POJ 2479

---恢复内容开始---
 1 #include <stdio.h>
 2 #include <iostream>
 3 
 4 using namespace std;
 5 
 6 int lef[50005],righ[50005];
 7 
 8 int main()
 9 {
10     int n,t,a[50005];
11     scanf("%d",&t);
12     while(t--)
13     {
14         scanf("%d",&n);
15         for(int i=0;i<n;i++)
16             scanf("%d",&a[i]);
17         lef[0]=a[0];
18         for(int i=1;i<n;i++)
19             if(lef[i-1]<0) lef[i]=a[i];
20             else lef[i]=lef[i-1]+a[i];
21         for(int i=1;i<n;i++)
22             lef[i]=max(lef[i],lef[i-1]);
23         righ[n-1]=a[n-1];
24         for(int j=n-2;j>=0;j--)
25             if(righ[j+1]<0) righ[j]=a[j];
26             else righ[j]=righ[j+1]+a[j];
27         for(int j=n-2;j>=0;j--)
28             righ[j]=max(righ[j+1],righ[j]);
29         int ans=-11111111;
30         for(int i=1;i<n;i++)
31             ans=max(ans,righ[i]+lef[i-1]);
32         printf("%d
",ans);
33     }
34     return 0;
35 }
---恢复内容结束---