如何计算 (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是我们要求和的子网格width/height，即 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 是可变的。

如何计算 (O)N 中的最高总和

how to compute highest sum in (O)N

java

big-o