最大的子序列和问题

最大的子序列和问题描述：
给定整数A1,A2，…,AN,求SUM(Ak),k从i到j，的最大值。为了方便起见，如果所有整数均为
负数，则最大子序列和为0。

例：
输入-2,11,-4,13,-5,-2时，答案为20(从A2到A4)

最大子序列和问题的解。
算法一：
穷举,复杂度为O（N^3）

int maxsubsequencesum(const int A[],int N){
    int thissum,maxsum,i,j,k;
   
    maxsum=0;
    for(i=0;i<N;i++)
        for(j=i;j<N;j++){
                thissum=0;
                for(k=i;k<=j;k++)
                        thissum += A[k];
               
                if(thissum > maxsum)
                        maxsum = thissum;
        }
    return maxsum;
}

算法二：
对算法一进行优化，减少内循环，复杂度为O(N^2)

int maxsubsequencesum_2(const int A[],int N){
    int thissum,maxsum,i,j;
   
    maxsum=0;
    for(i=0;i<N;i++){
        thissum=0;
        for(j=i;j<N;j++){
             thissum += A[j];
                    
             if(thissum > maxsum)
                   maxsum = thissum;
        }
    }
    return maxsum;
}

算法三：
分治：最大子序列可能在三处出现，或者整个出现在数据的左半部，或者整个出现在右半部，
或者跨越输入数据的中部而占据左右两半部分。前两种情况可以递归求解，第三种情况的最
大和可以通过求出前半部分的最大和（包含前半部分的最后一个元素）以及后半部分的最大
和（包含后半部分的第一个元素），将这两个和相加而得到。
复杂度为O（NlgN）

int maxsubsum(const int A[], int left,int right){
    int maxleftsum,maxrightsum;
    int maxleftbordersum,maxrightbordersum;/*包含边界的最大值*/
    int leftbordersum,rightbordersum;
    int center,i;

    if(left == right){
         if(A[left] > 0)
             return A[left];
         else
             return 0; /*由题给条件，负数的最大子序列长度为0*/
    }

    /* divide */
    center = (left + right)/2;
    maxleftsum = maxsubsum(A,left,center);
    maxrightsum = maxsubsum(A,center+1,right);

   /*conquer*/
   maxleftbordersum=0;
   leftbordersum=0;
   for(i=center; i>=left;i--){
       leftbordersum += A[i];
       if(leftbordersum > maxleftbordersum)
          maxleftbordersum = leftbordersum;
   }

  maxrightbordersum=0;
  rightbordersum=0;
  for(i=center+1; i <= right; i++){
      rightbordersum += A[i];
      if(rightbordersum > maxrightbordersum)
          maxrightbordersum = rightbordersum;
  }

  /* max3 取三者最大值 */
  return max3(maxleftsum, maxrightsum, maxleftbordersum + maxrightbordersum);
}

int maxsubsequencesum_3(const int A[], int N){
    return maxsubsum(A,0,N-1);
}

算法四：
在线算法，复杂度O(N),

int maxsubsequencesum(const int A[],int N){
    int thissum,maxsum,j;
    thissum = maxsum = 0;

    for(j=0; j < N; j++){
        thissum += A[j];
       
        if(thissum > maxsum)
            maxsum = thissum;
        else if(thissum < 0)
            thissum = 0;
    }
    return maxsum;
}