所以我有代表网格的二维矩阵。每个元素包含一个数字。
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次会正确吗？
最佳答案
在下面的答案中，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] aka 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是可变的。