algorithm - 获取总和最大的子矩阵？

Question

输入:一个二维数组 NxN - 矩阵 - 具有正元素和负元素。

输出:任何大小的子矩阵它的总和是所有可能子矩阵中的最大值。

要求:算法复杂度为O(N^3)

历史:在算法专家 Larry 和 Kadane 算法的修改版的帮助下，我设法部分解决了仅确定求和的问题 - 下面Java.
感谢 Ernesto，他设法解决了确定矩阵边界的其余问题，即左上角、右下角 - 下面是 Ruby。

Answer 1

这是与发布的代码一起使用的解释。有两个关键技巧可以使这项工作有效进行:(I) Kadane 算法和 (II) 使用前缀和。您还需要 (III) 将技巧应用于矩阵。

第一部分:Kadane 的算法

Kadane 算法是一种寻找具有最大总和的连续子序列的方法。让我们从寻找最大连续子序列的蛮力方法开始，然后考虑对其进行优化以获得 Kadane 算法。

假设你有序列:

-1,  2,  3, -2

对于蛮力方法，沿着序列生成所有可能的子序列，如下所示。考虑到所有可能性，我们可以在每一步开始、扩展或结束一个列表。

At index 0, we consider appending the -1
-1,  2,  3, -2
 ^
Possible subsequences:
-1   [sum -1]

At index 1, we consider appending the 2
-1,  2,  3, -2
     ^
Possible subsequences:
-1 (end)      [sum -1]
-1,  2        [sum  1]
 2            [sum  2]

At index 2, we consider appending the 3
-1,  2,  3, -2
         ^
Possible subsequences:
-1, (end)       [sum -1]
-1,  2 (end)    [sum -1]
 2 (end)        [sum 2]
-1,  2,  3      [sum 4]
 2,  3          [sum 5]
 3              [sum 3]

At index 3, we consider appending the -2
-1,  2,  3, -2
             ^
Possible subsequences:
-1, (end)          [sum -1]
-1,  2 (end)       [sum  1]
 2 (end)           [sum  2]
-1,  2  3 (end)    [sum  4]
 2,  3 (end)       [sum  5]
 3, (end)          [sum  3]
-1,  2,  3, -2     [sum  2]
 2,  3, -2         [sum  3]
 3, -2             [sum  1]
-2                 [sum -2]

对于这种蛮力方法，我们最终选择了总和最好的列表 (2, 3)，这就是答案。然而，为了提高效率，考虑到您真的不需要保留每一个列表。在未结束的列表中，你只需要保留最好的一个，其他的不能做的更好。在已结束的列表中，您可能只需要保留最好的一个，并且前提是它比未结束的列表更好。

因此，您只需使用一个位置数组和一个求和数组即可跟踪您需要的内容。位置数组定义如下:position[r] = s 跟踪以 r 结束并从 s 开始的列表。并且，sum[r] 给出以 index r 结尾的子序列的总和。这是 Kadane 算法的优化方法。

再次运行示例，以这种方式跟踪我们的进度:

At index 0, we consider appending the -1
-1,  2,  3, -2
 ^
We start a new subsequence for the first element.
position[0] = 0
sum[0] = -1

At index 1, we consider appending the 2
-1,  2,  3, -2
     ^
We choose to start a new subsequence because that gives a higher sum than extending.
position[0] = 0      sum[0] = -1
position[1] = 1      sum[1] = 2


At index 2, we consider appending the 3
-1,  2,  3, -2
         ^
We choose to extend a subsequence because that gives a higher sum than starting a new one.
position[0] = 0      sum[0] = -1
position[1] = 1      sum[1] = 2
position[2] = 1      sum[2] = 5

Again, we choose to extend because that gives a higher sum that starting a new one.
-1,  2,  3, -2
             ^
position[0] = 0      sum[0] = -1
position[1] = 1      sum[1] = 2
position[2] = 1      sum[2] = 5
positions[3] = 3     sum[3] = 3

同样，最佳和是 5，列表是从索引 1 到索引 2，即 (2, 3)。

第二部分:前缀和

我们希望有一种方法来计算沿行的总和，对于任何起点到任何终点。我想在 O(1) 时间内计算该总和，而不是仅仅相加，这需要 O(m) 时间，其中 m 是总和中元素的数量。通过一些预先计算，这是可以实现的。就是这样。假设你有一个矩阵:

a   d   g
b   e   h 
c   f   i

你可以预先计算这个矩阵:

a      d      g
a+b    d+e    g+h
a+b+c  d+e+f  g+h+i

一旦完成，您只需减去两个值就可以得到从列中从任何起点到终点的任何列的总和。

第三部分:综合技巧寻找最大子矩阵

假设您知道最大子矩阵的顶行和底行。你可以这样做:

1. 忽略顶行上方的行并忽略底部下方的行行。
2. 利用剩下的矩阵，考虑使用每一列的总和来形成一个序列(有点像代表多行的行)。(您可以使用前缀快速计算此序列的任何元素求和法。)
3. 使用 Kadane 的方法找出最佳子序列顺序。你得到的索引会告诉你左右最佳子矩阵的位置。

现在，实际计算出顶部和底部行怎么样？只是尝试所有的可能性。尝试将顶部放在任何位置，将底部放在任何位置，然后针对每种可能性运行之前描述的 Kadane-base 程序。当您找到最大值时，您会跟踪顶部和底部位置。

查找行和列需要 O(M^2)，其中 M 是行数。查找列需要 O(N) 时间，其中 N 是列数。所以总时间是 O(M^2 * N)。并且，如果 M=N，则所需时间为 O(N^3)。