d(A) = max{sum(a[s1]..a[t1]) + sum(a[s2]..a[t2]) | 1<=s1<=t1<s2<=t2<=n}

即求两个子序列和的和的最大值。

为单个区间子序列和的最大值的变形。

左边的从左向右扫描，而右边的从右向左扫描即可。

#include<cstdio>

#include<algorithm>

using namespace std;

const int MAXN=50000+10;

int left[MAXN],right[MAXN],a[MAXN];

int main()

{

	int T;

	scanf("%d",&T);

	while(T--)

	{

		int n;

		scanf("%d",&n);

		for(int i=0;i<n;i++)

			scanf("%d",&a[i]);

		left[0]=a[0];

		right[n-1]=a[n-1];

		for(int i=1,j=n-2;i<n;i++,j--)

		{

			if(left[i-1]<0)

				left[i]=a[i];

			else

				left[i]=a[i]+left[i-1];

			if(right[j+1]<0)

				right[j]=a[j];

			else

				right[j]=a[j]+right[j+1];

		}

		for(int i=1,j=n-2;i<n;i++,j--)

		{

			left[i]=max(left[i],left[i-1]);

			right[j]=max(right[j+1],right[j]);

		}

		int ans=INT_MIN;

		for(int i=1;i<n;i++)

		{

			ans=max(ans,left[i-1]+right[i]);

		}

		printf("%d\n",ans);

	}

}

而POJ的2593 Max Sequence 也一样

把数组大小改改，输入的改改即可。

就不贴代码了