poj 2479 Maximum sum 最大连续子串的变异

http://poj.org/problem?id=2479

考察点：对连续子串的灵活应用

思路：

1，两个连续子串的最大和，他们必有一个分界点记为n,n前面的子串为连续串的最大和，n（包括n）后面的子串也是连续串的最大和。所以只要我们以n点为入口进行构思

2，我们先记录从左到右的连续串的最大值，记录在一个数组Ldp[]中，Ldp[]为到n点的连续子串的最大值。

3，然后我们记录从右到左的连续窜的最大值Rdp[],Rdp[i]为从右到左的第n个连续窜的最大值。

4，让后我们一一枚举分界点n，（2到最后），用Max记录最大值。

提交情况：自己不会灵活应用，看到别人的思路后，自己敲得代码，感觉自己弱爆了；

收获：可以对串灵活的应用，并且巩固了连续串的最大值求法，也知道连续窜的一个重要顺序：以后要谨记（t>max）Max=t;if(t<0)t=0;dp[i]=Max;不然很容易出错；

#include<stdio.h>
 #include<string.h>
 #include<iostream>
 #include<algorithm>
 using namespace std;
 #define INF -99999999


 int Ldp[50010];
 int Rdp[50010];
 int a[50010];


 int main()
 {
     int T;
     int n;
     int i;
     int Max;
     int t;
     scanf("%d",&T);
     while(T--)
     {
         memset(Ldp,0,sizeof(Ldp));
         memset(Rdp,0,sizeof(Rdp));
         scanf("%d",&n);
         Max=INF;
         t=0;
         for(i=1;i<=n;i++)
         {
             scanf("%d",&a[i]);
             t+=a[i];
             if(t>Max)
                 Max=t;
             if(t<0)
                 t=0;
             Ldp[i]=Max;
         }//求Ldp[]
         Max=INF;
         t=0;
         for(i=n;i>=0;i--)
         {
             t+=a[i];
             if(t>Max)
                 Max=t;
             if(t<0)
                 t=0;
             Rdp[i]=Max;
         }//求Rdp[],
         Max=INF;
         for(i=2;i<=n;i++)
             if(Ldp[i-1]+Rdp[i]>Max)
                 Max=Ldp[i-1]+Rdp[i];//以2到n为分界点，找出Max
         printf("%d\n",Max);
     }
     return 0;
 }