2479 Maximum sum

問題概要

数列A={a1,a2,...,an}に対して
d(A)=max{Σ[i=s1,t1]a[i] + Σ[i=s2,t2]a[i]|1≦s1≦t1＜s2≦t2≦n}
で定める。d(A)を求めよ。

n≦50000以下である。

解法

数列の区間[0,i]の中の連続する部分数列の和の最大値は、全てのiに対してまとめてO(n)で以下のように求められる。

dp[i]:i番目までの連続する部分数列の和の最大値
dp2[i]:i番目までの連続する部分数列のうち、a[i]を含むようなものの和の最大値

とすれば、
dp2[i]=max(a[i],dp2[i-1]+a[i])
dp[i]=max(dp[i-1],dp2[i])

これを両端からやり、表を作っておいた上で、二つの数列の区切りをn-1通り試せばよい。

ソースコード

int T,n,a[50000];
int h[50000],t[50000],c[50000];

void func(int *d){
	d[0]=c[0]=a[0];
	for(int i=1;i<n;i++){
		c[i]=max(c[i-1],0)+a[i];
		d[i]=max(d[i-1],c[i]);
	}
}
int main(){
	scanf("%d",&T);
	rep(U,T){
		scanf("%d",&n);
		rep(i,n)scanf("%d",a+i);
		func(h);
		reverse(a,a+n); func(t);
		
		int ans=-(1<<30);
		rep(i,n-1)ans=max(ans,h[i]+t[n-2-i]);
		printf("%d\n",ans);
	}
	return 0;
}