poj 2479 max sum

1

10
1 -1 2 2 3 -3 4 -4 5 -5

13
题意分析：求从左至右的最大的连续子序列的和然后在从右至左的一段连续子序列的和，但是这两段区间不能重叠；
简单的DP：
#include<iostream>
#define max(a,b) a>b?a:b
using namespace std;
int sum[50010],dp1[50010],dp2[50010];
int a[50010];
int main()
{
  int i,j,t,n;
  int maxn;
  int N;
  cin>>N;
  while(N--)
  {
   cin>>n;
   maxn=-0x3fffffff;
   for(i=1;i<=n;i++)
   {
  scanf("%d",a+i);
   }
   sum[1]=a[1];
   dp1[1]=a[1];
   for(i=2;i<=n;i++)
   {
     sum[i]=max(sum[i-1]+a[i],a[i]);
	 maxn=max(sum[i],maxn);
	 dp1[i]=maxn;
   }
    
     maxn=-0x3fffffff;
	dp2[n]=sum[n]=a[n];
	 for(i=n-1;i>=1;i--)
	 {
	   sum[i]=max(sum[i+1]+a[i],a[i]);
	   maxn=max(maxn,sum[i]);
       dp2[i]=maxn;
	 }
    maxn=-0x3fffffff;
	for(i=1;i<n;i++)
	{
	  int temp=dp1[i]+dp2[i+1];
	  maxn=max(maxn,temp);
	}
	if(N!=1) cout<<endl;
	cout<<maxn<<endl;
  }
  return 0;
}