学步园

POJ 2479 最大子段和

POJ 2479严格来说不是单纯的最大子段和，它是一个双向的最大子段和，为了弄清双向的最大子段和就必须弄清楚单向的最大子序和。

单向最大子段和问题如下：

在序列A[1..n](任意一个Ai都是整数,有正有负)中找出一个子序列A[p..q]使得M=Ap+Ap+1+…+Aq-1+Aq最大

例如如下的序列：

1 7 -8 -4 5 10 -9 -5

最大的一段是从{5,10}和为15

为使M最大，则A[p]和A[q]必须为正数，(在q-p>=1情况下)

如果A[p]为负数，那么为使M最大，可以舍弃A[p]，只取A[p+1..q]的序列（一个数加上一个负数会变小，要使和最大不如不要这个负数）A[q]必须为正也是同样的道理。

再推广结论，子序列A[p..q]中A[p..k]的子子序列和也必须为正(p<=k<=q)，因为A[p..k]的和可以看成一个数，它是在最优子序列的最左边的，若它是负数，那么A[k+1..q]的序列和将更大，同样地，A[k+1,.q]必须为正。

于是就有了这样的想法：

最优子序列A[p..q]一定是在A[1..n]中的，它的左边A[1..p-1]一定是负值或不存在，它的右边A[q+1..n]也一定是负值或不存在。但满足左边子子序列是负的，右边子子序列也是负的的子序列不一定是最优的，我可以比较所有这些序列的和，取其中的最大值。

于是设一个变量i来从左向右遍历序列，并分别求出A[1..i]中最大子序列的和sum，用max来记录子序列的最大值。

开始在i累加的过程中，使sum累加A[i]

那么就有了两种情况:

1.累加过程中sum<0 例如 A[1]为负值（此时sum=A[1]），那么A[1]不可能是最优子序列的左边部分，如果它是最优子序列的左边部分，那么它一定大于零，这里产生了矛盾，此时就需要重置sum为0，从A[2]再开始累加，若A[2]也小于零，再重置为0，从A[3]开始累加，以此类推。

2.累加过程中sum>0 例如A[1]为正的（此时sum=A[1]），那么A[1]就很有可能是最优子序列的左边部分，将sum与max比较，维护max的值。若A[2]也是正的（sum=A[1]+A[2]）也需要维护max，及时更新max的值。

在sum>0的情况中又会有两种情况出现:

要加的下一个值为负值

a.加上这个负数后sum仍然为正值，此时sum不会被置零，max值不会更新。（此时sum较之前变小了，max保存的是前面计算的子序列的和）

b.加上这个负数后sum为负值，此时就要置零sum，重新来计算下一个可能的最优子序列，此时max值保存的是左边的可能最优子序列的值。

以此进行下去，直到遍历完整个序列。

sum的值维护了子序列的左边界，max的值维护了子学列的右边界，都来保证子序列的和最大。

上述分析可写成下面的伪代码：

sum = A[1] //初始化
max = -∞
for i <- 2 to n //2到n遍历，初始化时已经算上A[1]了
　　if sum < 0 //sum小于零
　　    sum = A[i] //重置sum
　　else  //sum大于零
　　    sum += A[i] //累加sum
　　if sum > max //维护max值
　　    max = sum

简化的C代码:

sum = 0;
max = -∞;
for(i=1;i<=n;i++) {
　　sum += A[i];
　　if(sum<0)
　　    sum = 0;
　　if(sum>max)
　　    max = sum;
}

细节的地方：

有些地方往往没有说序列有正有负，可能全是负数，此时就会出现一个麻烦：上面的代码执行完后，最大为0.

有可能序列的第一个值就是负值，这时执行代码时，sum不是被处理成了0就是被处理成了第二值，导致max值在i=1的时候不准确,这一点在需要打表的地方尤为重要，然而POJ 2479正是在这里为难大家。

那么应该怎么改呢？

既然只是第一个值的问题，那么就可以对第一个值进行特殊处理，令max=A[1],就能解决这个问题

于是改过的代码就是:

sum = 0;
max = A[1];
for(i=1;i<=n;i++) {
　　sum += A[i];
　　if(sum>max)	//一定要先比较
　　    max = sum;
　　if(sum<0)
　　    sum = 0;
}

来看一看上下两段代码处理这两个序列的不同结果:

1.

-3 4 6 1 -3

对结果无太大影响,最终都是11

2.

-2 -3 -5 -1 -4

如果碰上了全负的序列，未注意细节的算法就是一场灾难。

POJ 2479中就需要注意这样的细节，双向的最大子序和问题关键在于分割，可将序列从A[k]处分开成A[1..k],A[k+1..n]（1<k<n）的两个子序列,在分别对A[1.k],A[k+1..n]求最大子序和,再把两者相加和总的最大值比较。

在实际的过程中，先会遍历k从1到n-1，求出A[1.k]的最大子序和，打一个表比方说叫left[k]，再遍历k从n到2，求出A[k..n]的最大子序和，再打一个表比方叫right[k]，再遍历k从1到n-1，求出最大的left[k]+right[k+1]

转移方程为:

res = max{left[k]+right[k+1],1<=k<=n-1}

AC代码:

#include <stdio.h>

int data[50005];//数据 
int left[50005];//left[i]表示从1到i的最大子序和值 
int right[50005];//right[i]表示从i到n的最大子序和值 

int main()
{
	int T,n,i,j,sum,max=-(1<<30);
	
	scanf("%d",&T); 
	
	for(i=0;i<T;i++) {//对每一组数据 
		scanf("%d",&n);
		for(j=1;j<=n;j++) {//读入数据 
			scanf("%d",&data[j]);
		}
		//-----------计算左边--------------- 
		sum = data[1];
		max = data[1];
		left[1] = data[1];
		for(j=2;j<=n;j++) {
			if(sum < 0)
				sum = data[j];
			else 
				sum += data[j];
			if(sum > max) {
				max = sum;
			}
			left[j] = max;
		}
		//--------------------------------
		
		//-----------计算右边-------------- 
		max = data[n];
		sum = data[n];
		right[n] = data[n];
		for(j=n-1;j>=1;j--) {
			if(sum < 0)
				sum = data[j];
			else 
				sum += data[j];
			if(sum > max) {
				max = sum;
			}
			right[j] = max;
		}
		//------------------------------- 
		max = -(1<<30);
		for(j=1;j<=n-1;j++) {//寻找最大值 
			if(left[j]+right[j+1]>max)
				max = left[j]+right[j+1];
		}
		
		printf("%d\n",max);
	}
	
	return 0;
}