как вычислить наибольшую сумму в (O) N - PullRequest
Новая
       20

как вычислить наибольшую сумму в (O) N

0 голосов
/ 29 апреля 2020

Итак, у меня есть 2d матрица, которая представляет сетку. Каждый элемент содержит число. 

     0   1   2   3
     -   -   -   -
0 -| 1 | 2 | 4 | 2 |
1 -| 2 | 5 | 1 | 3 |
2 -| 1 | 3 | 1 | 6 |
3 -| 3 | 4 | 5 | 1 |

Учитывая меньший квадрат (скажем, 2 x 2), найдите наибольшую квадратную сумму. Таким образом, каждая ячейка в квадрате суммируется в общей сумме.

Я не могу придумать способ сделать это без итерации по квадрату 2 * 2 для каждой ячейки.

Теперь я пытаюсь найти способ express этот метод, так что в худшем случае его O (N). Что означает для этого примера, что в худшем случае поиск будет корректным 16 раз?

1 Ответ

0 голосов
/ 29 апреля 2020

В ответе ниже n - это общий размер сетки, т.е. общее количество ячеек, а q - ширина / высота подсетки, которую мы хотим суммировать, т.е. q=2 - это пример.

Учитывая входную матрицу из вопроса, скажем, что мы находимся в указанном месте для 2x2, и мы знаем, что сумма равна 11. 

┌───┬───┬───┬───┐       ┌───┬───┬───┬───┐
│ 1 │ 2 │ 4 │ 2 │       │ 1 │ 2 │ 4 │ 2 │
╠═══╪═══╬───┼───┤       ├───╬═══╪═══╬───┤
║ 2 │ 5 ║ 1 │ 3 │       │ 2 ║ 5 │ 1 ║ 3 │
╟───┼───╫───┼───┤   →   ├───╫───┼───╫───┤
║ 1 │ 3 ║ 1 │ 6 │       │ 1 ║ 3 │ 1 ║ 6 │ 
╠═══╪═══╬───┼───┤       ├───╬═══╪═══╬───┤
│ 3 │ 4 │ 5 │ 1 │       │ 3 │ 4 │ 5 │ 1 │
└───┴───┴───┴───┘       └───┴───┴───┴───┘

Когда мы переходим к справа мы должны вычесть сумму старого левого столбца (2 + 1 = 3) и сложить сумму нового правого столбца (1 + 1 = 2), чтобы получить новую сумму 2x2, равную 10.

Однако высота столбца равна q, и мы хотим сделать это без влияния на сложность времени q.

Так что нам нужно запомнить сумму каждого столбца, для полной ширины сетки. Мы обновляем эту сумму для следующей строки, когда мы движемся вправо.

Когда мы сделали первый ряд матриц 2x2, мы получили следующие суммы столбцов: 

╔═══╤═══╤═══╤═══╗       ┌───┬───┬───┬───┐       ┌───┬───┬───┬───┐
║ 1 │ 2 │ 4 │ 2 ║       │ 1 │ 2 │ 4 │ 2 │       │ 1 │ 2 │ 4 │ 2 │
╟───┼───┼───┼───╢       ╠═══╪═══╬───┼───┤       ├───╬═══╪═══╬───┤
║ 2 │ 5 │ 1 │ 3 ║       ║ 2 │ 5 ║ 1 │ 3 │       │ 2 ║ 5 │ 1 ║ 3 │
╠═══╪═══╪═══╪═══╣   →   ╟───┼───╫───┼───┤   →   ├───╫───┼───╫───┤
│ 1 │ 3 │ 1 │ 6 │       ║ 1 │ 3 ║ 1 │ 6 │       │ 1 ║ 3 │ 1 ║ 6 │
├───┼───┼───┼───┤       ╠═══╪═══╬───┼───┤       ├───╬═══╪═══╬───┤
│ 3 │ 4 │ 5 │ 1 │       │ 3 │ 4 │ 5 │ 1 │       │ 3 │ 4 │ 5 │ 1 │
└───┴───┴───┴───┘       └───┴───┴───┴───┘       └───┴───┴───┴───┘
┌───┬───┬───┬───┐       ╔═══╤═══╦───┬───┐       ┌───╦═══╤═══╦───┐
│ 3 │ 7 │ 5 │ 5 │       ║ 3 │ 8 ║ 5 │ 5 │       │ 3 ║ 8 │ 2 ║ 5 │  Column Sums
└───┴───┴───┴───┘       ╚═══╧═══╩───┴───┘       └───╩═══╧═══╩───┘

По мере движения из (x, y) = (0,1) в (1,1) мы можем легко вычесть старый левый столбец, так как у нас есть сумма 3 в columnSum[0].

Перед добавлением нового права Сумма столбца, нам нужно ее обновить, поэтому мы вычитаем (2,0) значение 4 и добавляем (2,2) значение 1, давая нам columnSum[2] += grid[2][2] - grid[0][2] aka 5 + 1 - 4 = 2.

Это фиксированная стоимость , не имеет отношения к q, хотя для вычисления этого используется значение q, чтобы вычислить смещение ячеек для сложения и вычитания.

Say x,y - верхний левый угол субматрица, затем шаги для перемещения вправо: 

columnSum[x + q] += grid[y + q - 1][x + q] - grid[y - 1][x + q];
sum += columnSum[x + q] - columnSum[x];
x++;

Как видите, код использует q, но имеет O (1) сложность относительно q.

Полный код, конечно, более сложный, он начинается и продвигается к следующему ряду, но это суть того, как выполнить операцию с временная сложность O (n) , даже когда q является переменным.

...