0

在“编程珍珠”第8栏。存在最大子数组问题。

问题 :

输入是一个包含 n 个浮点数的向量 x;输出是在输入的任何连续子向量中找到的最大和。为了完成问题定义,我们将说当所有输入为负时,最大和子向量是空向量,其和为零。

最有效的解决方案:

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

本专栏有一个练习: 我们将负数数组的最大子向量定义为零,即空子向量之和。假设我们将最大子向量定义为最大元素的值;您将如何更改各种程序?

我对这个练习有两个问题 (1)我对“假设我们已经将最大子向量定义为最大元素的值”感到有点困惑。这是否意味着负数数组的最大子向量是数组中的最大元素?

例如:数组:[-1 -2 -3],最大子向量:-1 数组:[-1 2 3],最大子向量:[2 3]

对不起这个愚蠢的问题,英语不是我天真的语言。

(2)作者给出了解决方案:“将赋值maxsofar=0替换为maxsofar = -infinity。” 根据我对问题的理解,这个解决方案似乎是不正确的。

例如:数组:[-1 -2 -3],答案应该是-1。但是根据解决方案,它是0。

谢谢,

4

1 回答 1

1

我同意你的看法。如果作者的解决方案只是改变 maxsofar 的初始化,那么它根本不会改变算法。

于 2012-06-22T18:33:47.593 回答