最大子列和问题

方法一：

 1 int MaxSubseqSum1(int a[],int n)
 2 {
 3     int ThisSum,MaxSum=0;
 4     int i,j,k;
 5     for(i=0;i<N;i++){//i是子列左端位置
 6             for(j=i;j<N;j++){//j是子列右端的位置
 7                     ThisSum=0;//ThisSum是从A[i]到A[j]的子列和
 8             for(k=i;k<=j;k++)
 9                 ThisSum+=A[k];
10             if(ThisSum>MaxSum)//如果得到的这个子列和更大，则更新
11                 MaxSum=ThisSum;
12 
13             }
14     }
15     return MaxSum;
16 }

时间复杂度为O(n³)。
方法二：

 1 int MaxSubseqSum2(int A[],int n)
 2 {
 3     int ThisSum,MaxSum=0;
 4     int i,j;
 5     for(i=0;i<N;i++)
 6     {
 7         ThisSum=0;
 8         for(j=i;j<N;j++)
 9         {
10             ThisSum+=A[j];
11         if(ThisSum>MaxSum)
12             MaxSum=ThisSum;
13         }
14     }
15     return MaxSum;
16 }

时间复杂度为O(n²)。
方法三：

分而治之

时间复杂度为O(nlgn)。

方法四：

 1 int MaxSubseqSum3(int A[],int N)
 2 {
 3     int ThisSum,MaxSum;
 4     int i;
 5     ThisSum=MaxSum=0;
 6     for(i=0;i<N;i++)
 7     {
 8         ThisSum+=A[i];
 9         if(ThisSum>MaxSum)
10             MaxSum=ThisSum;
11         else if(ThisSum<0)/*如果当前子列和为负，则不可能使后面的部分和增大，抛弃之*/
12             ThisSum=0;
13     }
14     return MaxSum;
15 }

时间复杂度为O(n)。