求最大子列和问题 在线处理法（动态规划法）

基本思想：

当当前最大子列和为负数时，抛弃当前子列和（置为0）因为一个负数与后面的数相加只会使这个和更小，否则加上一个数，再进行判断，若为负数则抛弃，若比当前最大子列和大则更新当前子列和

举例说明，假如当前有

-1，3，-2，4，-6，1，6，-1 求最大子列和

第一次子列为-1， 当前子列和为-1 抛弃 最大子列和为0

第二次为3，子列和为3 更新 最大子列和为3

第三次为3-2=1， 子列和为1 什么也不做 最大子列和为3

第四次为1+4=5，子列和为5 更新 最大子列和为5

第五次为5-6=-1，子列和为-1 抛弃 最大子列和为0

第六次为-1+6=5，子列和为5 更新 最大子列和为5

第七次为5-1=4，子列和为4 什么也不做 最大子列和为5

‘在线’的意思是指每输入一个数据就进行即时处理，在任何一个地方中止输入，算法都能正确给出当前的解

int MaxSubseqSum4(int A[],int N){
    int ThisSum,MaxSum;
    int i;
    ThisSum=MaxSum=0;
    for(i=0;i<N;i++){
        ThisSum+=A[i]/*向右累加*/
        if(ThisSum>MaxSum)
            MaxSum=ThisSum;/*发现更大和则更新当前结果*/
        else if(ThisSum<0)/*如果当前子列和为负*/
            ThisSum=0;/*则不可能使后面的部分和增大，则抛弃之*/
    }
    return MaxSum;
}

因为只有一层for循环，所以时间复杂度为T(N)=O(N)，效率非常高