java - 如何计算 (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是我们想要的子网格的宽度/高度sum，即 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 是可变的。