如何理解最大子序列和的在线算法

（1）先给出在线算法的伪代码，仅针对至少含有一个正数的序列：

Solve_MaxSubSum(A, n):
    sum <- 0
    maxsum <- 0
    boundleft <- 0
    for i <- 0 to n-1 do
        sum <- sum + A[i]
        if sum <= 0 then
            sum <- 0
            boundleft <- i + 1
        else if sum > maxsum then
            maxsum <- sum
            boundright <- i

maxsum = A[boundleft] + ... + A[boundright]

接下来，用以下序列举例说明在线算法的详细步骤

可以看出，在线算法仅扫描一遍序列即可求得最大子序列；其高效的本质在于当子序列和为非正数时，该序列要被弃掉而要从序列之后的元素开始往后扫描。

（2）疑问一：当子序列之和为非正数时，为何不能继续使用该序列？

此问题比较简单，反证法即可证明。假设此序列为seqone，且作为序列seqtwo的头部序列。

由于seqone是seqtwo的头部序列，seqtwo删除seqone后不影响剩余元素的连续性；

再由于seqone的序列和为非正数，seqtwo删除seqone后序列和一定不会减小，甚至可能增大；

因此对于seqtwo来说，seqone没有保留的必要。

（3）疑问二：当子序列之和为非正数时，为何不从子序列中的任一元素开始往后扫描，而是从子序列之后的元素开始扫描？

要回答这个问题，我们截取算法步骤中的一部分来说明，假设算法从A[i]开始往后扫描，直到遇到A[k]，序列和才小于或等于0。

此时我们有以下条件：

条件（a）： 

条件（b）：

接下来，我们不遵循在线算法的步骤（从序列之后的元素开始扫描），而是任取位于和之间的某一元素开始往后扫描，假设此元素是：

可以证明 以为首端且末端不超过的任一序列之和，一定小于当前最大子序列和。

假设这段序列是，那么一定成立，否则，违反了条件（b）。

因此，，证毕。

换句话解释这个结论，即当子序列之和为非正数时，没有必要再从子序列中的任一元素开始往后扫描。