最大的子序列和问题描述：
给定整数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;
}
