求最大子列和问题 优化算法

先看一下前面的传统算法：

intMaxSubseqSum1(intA[],intN){
    intThisSum,MaxSum=0;
    inti,j,k;
    for(i=0;i<N;i++){/*i是子列左端位置*/
        for(j=i;j<N;j++){/*j是子列右端位置*/
            ThisSum=0;/*ThisSum是从A[i]到A[j]的子列和*/
            for(l=i;k<=j;k++)
                ThisSum+=A[k];
                if(ThisSum>MaxSum)/*如果刚得到的这个子列和更大*/
                MaxSum=ThisSum;/*则更新结果*/
        }/*j循环结束*/
    }/*i循环结束*/
    returnMaxSum;
}

时间复杂度为:T(N)=O(N^3)，显然该算法虽然简单易懂，但是时间复杂度太高。

分析一下这个算法，前三项的连续子列为

a1;

a1+a2;

a1+a2+a3;

第三次相加的时候重复了第二次的a2+a3的操作，然而仅仅需要再第二次的基础上加a3即可，这样就减少了一层的for循环，时间复杂度为T(N)=O(N^2)，效率大大提高；
代码如下：

int Ma`xSunseqSum2(int A[],int N){
    int ThisSum,MaxSum=0;
    int i,j;
    for(i=0;i<N;i++){/*i是子列左端位置*/
        ThisSum=0;/*ThisSum是从A[i]到A[j]的子列和*/
        for(j=i;j<N;j++){/*j是子列右端位置*/   
            ThisSum+=A[j];
            /*对于相同的i，不同的j，只要在j-1次循环的基础上累加1项即可*/
            if(ThisSum>MaxSum)/*如果刚得到的这个子列和更大*/
                MaxSum=ThisSum;/*则更新结果*/
        }/*j循环结束*/
    }/*i循环结束*/
    return MaxSum;
}