1

我目前正在阅读 Jon Bentley 的“Programming Pearls”，其中有一个我似乎无法回答的问题。这里是：

在最大子数组问题中，给定一个 nxn 实数数组，我们必须找到包含在任何矩形子数组中的最大和。

在本章中，它列出了一种求数组最大值的算法：
maxsofar = 0
maxendinghere = 0
for i = [0, n) // n) = n-1
/*ivariant: maxendinghere 和 maxsofar 对于 x[ 是准确的0…i-1] */
maxendinghere = mac(maxendinghere + x[i], 0)
maxsofar = mac(maxsofar, maxendinghere)

我正在考虑您是否可以按照 上面显示的算法 对所有行的
所有列说些什么

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

4

1 回答 1

2

首先，您必须了解一维数组版本：一维数组的最大连续和。

为了解决一维数组版本，算法很简单，你已经在上面给出了。

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

这是 O(n)。然后我们可以扩展到 2d 版本。对于 2d 版本，您可以将其转换为 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)

于 2013-02-06T01:33:53.180 回答