题目链接：https://vjudge.net/problem/POJ-2479

题意：给出n个数组成的序列，求将序列分成前后两部分时两部分最大连续子串的和的和的最大值。

思路：题意很简单，用dp1[i]表示以i为结尾的最大连续子串的和，dp2[i]表示以i为起始的最大连续子串的和，从1到n遍历计算出dp1，从n到1遍历计算出dp2。遍历同时维护数组Max1[i]，Max2[i]，分别表示[1,i]区间最大连续子串和，[i,n]区间最大连续子串和。最后遍历一遍找到Max1[i]+Max[i+1]的最大值即可。需要注意的是a[i]可能为负值，所以ans应初始化为0xcfcfcfcf。

AC代码：

#include
     
      #include
      
       using namespace std;int T,n,a[50005],dp1[50005],dp2[50005],Max1[50005],Max2[50005];int ans;int main(){    scanf("%d",&T);    while(T--){        scanf("%d",&n);        for(int i=1;i<=n;++i)            scanf("%d",&a[i]);        dp1[1]=a[1],dp2[n]=a[n];        Max1[1]=a[1],Max2[n]=a[n];        for(int i=2;i<=n;++i){            dp1[i]=max(dp1[i-1]+a[i],a[i]);            Max1[i]=max(Max1[i-1],dp1[i]);        }        for(int i=n-1;i>=1;--i){            dp2[i]=max(dp2[i+1]+a[i],a[i]);            Max2[i]=max(Max2[i+1],dp2[i]);        }        ans=0xcfcfcfcf;        for(int i=1;i
       
        ans)                ans=Max1[i]+Max2[i+1];        printf("%d\n",ans);    }    return 0;}