如何计算（O）N中的最高和

Question

因此，我有一个表示网格的二维矩阵。每个元素包含一个数字。

     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的平方迭代。

现在，我正在尝试寻找一种表达此方法的方法，以便使它的O（N）最差。这意味着在此示例中，最坏的搜索结果将正确16倍？

Answer 1

在下面的答案中，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）时，我们很容易减去旧的左列，因为在columnSum[0]中有总和3。

在添加新的右列的总和之前，我们需要对其进行更新，因此我们减去（2,0）值4并加上（2,2）值1，得到columnSum[2] += grid[2][2] - grid[0][2]亦称5 + 1 - 4 = 2。

这是固定成本，与q无关，尽管在计算时使用q的值，以便计算要添加和减去的像元的偏移量。

说x,y是子矩阵的左上角，那么向右移动的步骤是：

columnSum[x + q] += grid[y + q - 1][x + q] - grid[y - 1][x + q];
sum += columnSum[x + q] - columnSum[x];
x++;
如您所见，代码使用q，但相对于q具有O（1）

复杂度。

完整的代码当然会更复杂，需要入门并继续进行到下一行，但这是如何以时间复杂度O（n）

进行操作的本质，即使q是可变的。