求最大子列和问题（浙江大学数据结构）

问题陈述：

　　给定N个整数的序列{A₁, A₂, ... , A_N}，求函数ƒ(i, j) = max{0, A_i + A_i+1 + ... + A_j}(1<=i<j<=N)的最大值。

 

问题分析：

　　求给定数列的最大子列和。

方法一：暴力求解  ：遍历每个子序列。时间复杂度T(N)=N3。

int MaxSubseqSum1(int A[],int n)
{
int i,j,k;
int ThisSum,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;
}

方法二：对方法一的优化，即每个子序列的和是前一个子序列加上后一个的和。时间复杂度T(N)=N2。

int MaxSubseqSum2(int A[],int n)
{
int i,j,k;
int ThisSum,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;
}

方法三：分治法

时间复杂度：T(N)=2T(N/2)+CN

= 2² * T(N/2²) + c2N

　　 = 2^k * T(N/2^k) + ckN 其中 N/2^k = 1

        = N * T(1) + cNlog₂N

　　 = O(NlogN)

//第三种，分治法 
int Max(int A,int B,int C)
{
if(A>B&&A>C)
return A;
else
if(B>A&&B>C)
return B;
else
return C;
 } 
int PartSum(int A[],int left,int right)
{
int center,i;
int MaxLeftSum,MaxRightSum;
int LeftBorderSum=0,RightBorderSum=0;
int MaxLeftBorderSum=0,MaxRightBorderSum=0;
center=(left+right)/2;

//递归终止条件
if(left==right)
{
if(A[left]>0)
return A[left];
else
return 0;
}

//递归求左右两边的最大值
MaxLeftSum=PartSum(A,left,center);
MaxRightSum=PartSum(A,center+1,right);

//求经过center的最大子列值
for(i=center;i>=left;i--)
{
LeftBorderSum+=A[i];
if(LeftBorderSum>MaxLeftBorderSum)
MaxLeftBorderSum=LeftBorderSum;
}
for(i=center+1;i<=right;i++)
{
RightBorderSum+=A[i];
if(RightBorderSum>MaxRightBorderSum)
MaxRightBorderSum=RightBorderSum;
}

//返回分治部分的最大值
return Max(MaxLeftSum,MaxRightSum,(MaxLeftBorderSum+MaxRightBorderSum));
} 
int MaxSubseqSum3(int A[],int n)
{
return PartSum(A,0,n-1);
}

第四种（最简单）:在线处理(每输入一个数据就进行即时处理)，时间复杂度：T(N)=O(N)。

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;
}