<转>最大子序列的线性时间算法

Int MaxSubsequenceSum(const int A[], int N)
{
       int ThisSum, MaxSum, j;
       ThisSum = MaxSum = 0;
       For(j=0; j < N; j++)
       {
              ThisSum += A[j];
              If (ThisSum > MaxSum)
                     MaxSum = ThisSum;
              Else if(ThisSum < 0)
                     ThisSum = 0;
       }
       return MaxSum;
}

对于这个算法的分析(逻辑):

从左相右相加，若结果不断的增加，那么ThisSum将同MaxSum一起增加，如果遇到负数，那么也加到ThisSum上去，但是此时ThisSum < MaxSum，那么就不加。看ThisSum是不是会回升，若一直不回升，不断或是波浪型的下降，那么当它降到0时，说明前一段与后一段是可以抛弃的。正如有 7 ， -8 一样，我们可以不要这两个数，但是我们知道MaxSum依然保存着前一段的最大值，（这就是这个算法中的厉害，我认为）。然后，ThisSum将从后面开始将这个子段进行分析，若有比当前MaxSum大的子段，然后替换（此时可以彻底抛弃前一段）。这样一趟扫描结果也就出来了。

在序列中所有数都是负数的情况下不能用该算法，结果会返回0。考虑到这种情况，在应用此算法前只需增加一次遍历判断值是否都为负，是则返回序列中最大值，否则应用上面的算法，复杂度仍然是o(n)。