【两段连续不重合子序列和最大】动态规划-白红宇

【两段连续不重合子序列和最大】动态规划

阅读量：4452 次

发布时间：2019-06-07

本文共 1305 字，大约阅读时间需要 4 分钟。

最大子序列

TimeLimit: 1 Second MemoryLimit: 32 Megabyte

Totalsubmit: 156 Accepted: 42

Description

给定一个N个整数组成的序列，整数有正有负，找出两段不重叠的连续子序列，使得它们中整数的和最大。两段子序列都可以为空。

Input

多组输入，每组第一行为N，表示序列的长度；第二行为N个整数，表示输入序列。

0<N<=1,000,000

Output

对于每组输入，输出一行，仅一个整数，表示最大的和。

Sample Input

185 -580 -889 701 964 -878 353 -761 608

Sample Output

2273

Hint

样例输入序列的一种选择为：(701 964)和(608)，整数的范围为(-1000,1000)

#include 
      
       #include 
       
        using namespace std;const int INF=1000005;int s[INF],lt[INF],rt[INF],dp[INF];int main(){    //freopen("in.txt","r",stdin);    int i,n;    while(cin >> n)    {        for (i=1;i<=n;i++)scanf("%d",&s[i]);        dp[n+1]=dp[0]=-INF;        lt[0]=rt[n+1]=-INF;        for (i=1;i<=n;i++)//正向        {            dp[i] = max(dp[i-1]+s[i],s[i]);        }         for (i=1;i<=n;i++)         {             lt[i] = max(dp[i],lt[i-1]);//             lt[i] = dp[i];         }        for (i=n;i>=1;i--)  //逆向        {            dp[i] = max(dp[i+1]+s[i],s[i]);        }         for (i=n;i>=1;i--)         {             rt[i] = max(dp[i],rt[i+1]);//                rt[i] = dp[i];         }         int sum=-INF;//枚举        for (i=1;i<=n;i++)        {            sum = max(sum,lt[i]+rt[i+1]);        }        if(sum<=0)        cout <<'0' <