题目大意： 对整数串S,求其两个不相交的子串s1、s2,使得s1+s2的值最大。

方法：DP，

lt[i]代表以第i个元素结尾的串最大值

rt[i]代表以第i个元素开头的串的最大值

那么设置一个rtm[i]代表取后i个元素之中最大连续子串的和

很显然，lt[i]=max(a[i],lt[i-1]+a[i]);

rt[i]=max(a[i],rt[i+1]+a[i]);

rtm[i]=max(rtm[i+1],rt[i]);

#include 
     
      #include 
      
       using namespace std;#define max(a,b) a>b?a:b#define MAXV 50010#define inf -10010int lt[MAXV],rt[MAXV],a[MAXV],rtm[MAXV];int main(){    int t,n,i,temp;    scanf("%d",&t);    while(t--){        scanf("%d",&n);        for(i=1;i<=n;i++)            scanf("%d",&a[i]);        temp=inf;lt[1]=a[1];rt[n]=a[n];        for(i=2;i<=n;i++)        {            lt[i]=max(a[i],lt[i-1]+a[i]);               }        for(i=n-1;i>=1;i--)        {            rt[i]=max(a[i],rt[i+1]+a[i]);        }        rtm[n]=rt[n];        for(i=n-1;i>=1;i--)            rtm[i]=max(rtm[i+1],rt[i]);        int ma=inf;        for(i=2;i<=n;i++)        {            ma=max(ma,lt[i-1]+rtm[i]);        }        printf("%d\n",ma);    }    return 0;}
      
     

版权声明：本文为博主原创文章，未经博主允许不得转载。