动态编程.矩阵的最大子阵列

Question

我目前正在阅读Jon Bentley的《编程珍珠》，其中有一个问题我似乎无法回答。这是：

在最大子数组问题中，我们得到了实数的nxn数组，并且我们必须找到任何矩形子数组中包含的最大和

在本章中，它列出了一个查找数组最大值的算法：
maxsofar=0
maxendinghere=0
对于i=[0，n）//n）=n-1
/*ivariant:maxendinghere和maxsofar对于x[0]…i-1]*/
是精确的maxendinghere=mac（maxendingthere+x[i]，0）
maxsofar=mac（maxsofar，maxendinghere）

我在考虑你是否可以说一些类似
的话对于所有列
对于所有行
上面显示的算法

但我不确定这是否可行。有什么想法吗？

Answer 1

首先，你必须了解1d数组的版本：1d数组的最大连续和。

对于1d数组版本的求解，算法很简单，u已经给出了上面的内容。

maxsofar = 0
maxendinghere = 0
for i = [0, n)
    maxendinghere = max(maxendinghere + x[i], 0)
    maxsofar = max(maxsofar, maxendinghere)

这是O（n）。然后我们可以扩展到2d版本。对于2d版本，u可以将其转换为1d版本，并且仍然使用上述算法，但如何转换？只需将一列中的值相加，并将其视为新的1d数组。示例：

矩阵为2*2，如下所示：

1 2
3 4

总结之后，你可以得到

4 6

明白了吗？你所需要做的就是列举所有可能的方法来计算从第i行到第j行的列和。然后应用上述关键算法。伪代码：

for i=0 to n
    for j=i to n
        create a new array which contains the column sum from the ith row to jth row
        apply the above O(n) algorithm to get the maximum

总配合度为O（n^3）