1091. Maximum Sum

TAG 动态规划

设maxd[n]为前n个数的最大子序列和

maxd[n]=max{ maxd[n-1], sum[n]-minX } 其中，minX=min{sum[i] | 1<=i<n}

同理，设rmaxd[n]为从n到序列完的最大子序列和

则答案为max{ maxd[i]+rmaxd[i+1] },时间复杂度为O(n)

#include <stdio.h>
const int N=50000;
int ans;
int t,n;
int a[N];
int sum[N],rsum[N];
int maxd[N],rmaxd[N];
int minp;
int max(int a, int b)
{
	return a>b? a: b;
}
int min(int a,int b)
{
	return a<b? a: b;
}
int main(int argc, char *argv[])
{
	scanf("%d", &t);
	while ( t--)
	{
		scanf("%d", &n);
		for (int i=0; i<n; ++i)
		{
			scanf("%d", &a[i]);
		}
		sum[0]=a[0];
		rsum[n-1]=a[n-1];
		for (int i=1; i<n; ++i)
		{
			sum[i]=sum[i-1]+a[i];
			rsum[n-1-i]=rsum[n-i]+a[n-1-i];
		}
		maxd[0]=sum[0];
		minp=min(0,sum[0]);
		for (int i=1; i<n; ++i)
		{
			maxd[i]=max( maxd[i-1], sum[i]-minp );
			minp=min( minp, sum[i] );
		}
		rmaxd[n-1]=rsum[n-1];
		minp=min( 0,rsum[n-1] );
		for (int i=n-2; i>=0; --i)
		{
			rmaxd[i]=max( rmaxd[i+1], rsum[i]-minp);
			minp=min( minp, rsum[i] );
		}

		ans=sum[0]+rsum[1];
		for (int i=1; i<n-1; ++i )
		{
			ans=max( maxd[i]+rmaxd[i+1], ans);
		}
	
	    printf("%d/n",ans );
	}
	return 0;
}