我正在尝试编写一个解决最大子数组问题的程序。我可以理解一维阵列上的Kadane算法背后的直觉以及二维阵列上的O（N ^ 4）实现。但是，我在理解二维数组上的O（N ^ 3）实现时遇到了一些麻烦。
1）为什么我们将这些元素与同一列中前几行的元素相加？
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++)
array[i][j] += array[i-1][j];
}
2）我对算法的第二部分不了解
试图在网上寻找解释，但无济于事。希望在这里得到一些帮助！
提前致谢！
您知道如何使用Kadane算法在一维数组上计算最大和子数组。现在，我们想将此算法扩展到2D数组。对于O（N ^ 3）算法，我们有一个直觉。如果我们以某种方式创建N ^ 2个子问题，然后尝试运行O（N）Kadane算法，则可以解决最大子数组问题。
因此，基本上，我们如何创建N ^ 2子问题的方法是遍历矩阵的所有顶部和底部行。然后，我们尝试通过应用kadane的1D算法找到子数组存在的最佳列。因此，我们将这两行之间的数字按列进行求和，然后将kadane的1D算法应用于此新形成的1D数组。
但是我们这里有一个问题。计算顶行和底行的所有O（n ^ 2）范围的总和本身就是O（n ^ 4）。可以通过修改矩阵来克服瓶颈，方法是将每个元素替换为该元素列中位于其上方的所有数字的总和。因此，现在我们可以通过减去矩阵中的适当数组来找出O（n）时间中任意两行之间的数字总和。
Java伪代码-
int kadane2D(int array[N][M]){
// Modify the array's elements to now hold the sum
// of all the numbers that are above that element in its column
for (int i = 1; i < N; i++) {
for (int j = 0; j < M; j++){
array[i][j] += array[i-1][j];
}
}
int ans = 0; // Holds the maximum sum matrix found till now
for(int bottom = 0; bottom < N; bottom++){
for(int top = bottom; top < N; top++){
// loop over all the N^2 sub problems
int[] sums = new int[N];
// store the sum of numbers between the two rows
// in the sums array
for(int i = 0; i < M; i++){
if (bottom > 0) {
sums[i] = array[top][i] - array[bottom-1][i];
} else {
sums[i] = array[top][i];
}
}
// O(n) time to run 1D kadane's on this sums array
ans = Math.max(ans, kadane1d(sums));
}
}
return ans;
}
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句