在“编程珍珠”第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。
谢谢,