最大子阵列

Question

在“编程珍珠”栏8。有一个最大的子阵列问题。

问题：

输入是正的浮点数的向量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

感谢，

Answer 1

我同意你的看法。如果作者的解决方案只是改变maxsofar的初始化，那么它在所有算法中都不会改变。