求最大子序列的原理为什么它能工作?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;

求最大子序列的原理为什么它能工作?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;
求最大子序列的原理
为什么它能工作?
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;
}
这是《数据结构与算法分析》的例子,

求最大子序列的原理为什么它能工作?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;
在这一遍扫描数组当中,从左到右记录当前子序列的和ThisSum,若这个和不断增加,那么最大子序列的和MaxSum也不断增加(不断更新MaxSum).如果往前扫描中遇到负数,那么当前子序列的和将会减小.此时ThisSum 将会小于MaxSum,当然MaxSum也就不更新.如果ThisSum降到0时,说明前面已经扫描的那一段就可以抛弃了,这时将ThisSum置为0.然后,ThisSum将从后面开始将这个子段进行分析,若有比当前MaxSum大的子段,继续更新MaxSum.这样一趟扫描结果也就出来了.