Question

求最大子序列的原理

为什么它能工作？
int MaxSubSequenceSum( const int A[], int N)
{
int ThisSum, MaxSum, j;
MaxSum = 0;
for( j = 0; j < N; j++)
{
ThisSum += A[j];

if(ThisSum > MaxSum)
MaxSum = ThisSum;
else if(ThisSum < 0)
ThisSum = 0;
}
return ThisSum;
}
这是《数据结构与算法分析》的例子，请详细解释。

Answer 1

在这一遍扫描数组当中，从左到右记录当前子序列的和ThisSum，若这个和不断增加，那么最大子序列的和MaxSum也不断增加(不断更新MaxSum)。如果往前扫描中遇到负数，那么当前子序列的和将会减小。此时ThisSum 将会小于MaxSum，当然MaxSum也就不更新。如果ThisSum降到0时，说明前面已经扫描的那一段就可以抛弃了，这时将ThisSum置为0。然后，ThisSum将从后面开始将这个子段进行分析，若有比当前MaxSum大的子段，继续更新MaxSum。这样一趟扫描结果也就出来了。