Description

給定一個長度為n的整數序列，要求從中選出兩個連續子序列，使得這兩個連續子序列的序列和之和最大，最終只需輸出最大和。一個連續子序列的和為該子序列中所有數之和。每個連續子序列的最小長度為1，并且兩個連續子序列之間至少間隔一個數。

Input

第一行是一個整數表示n。

第二行是n個整數表示整數序列。

Output

一個數，兩個連續子序列的序列和之和。

動態規劃.這不某年初賽題

我們設\(l[i]\)代表從\(1\)到\(i\)的最大的子序列的和,\(r[i]\)代表從\(i\)到\(n\)的最大的子序列的和.（可以不包含\(i\)）

然后維護的話,每次轉移取\(max\)
\[ l[i]=max(l[i-1]+x[i],x[i])\\ r[i]=max(r[i+1]+x[i],x[i]) \]
然后取前綴\(max\)和后綴\(max\).

取\(ans\)的時候就是
\[ ans=max(ans,l[i-1]+r[i+1]) \]
(因為題目要求至少間隔一個數～w～

還有,由于可能出負數,所以\(l\)數組要從\(2\)開始.\(r\)數組要從\(n-1\)開始

代碼

#include<cstdio>
#include<cctype>
#include<iostream>
#define R register
using namespace std;
inline void in(int &x)
{int f=1;x=0;char s=getchar();while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}while(isdigit(s)){x=x*10+s-'0';s=getchar();}x*=f;
}
int n,ans=-2147483644;
int l[1000008],r[1000008],x[1000008];
int main()
{in(n);for(R int i=1;i<=n;i++)in(x[i]);l[1]=x[1];for(R int i=2;i<=n;i++)l[i]=max(l[i-1]+x[i],x[i]);for(R int i=2;i<=n;i++)l[i]=max(l[i-1],l[i]);r[n]=x[n];for(R int i=n-1;i>=1;i--)r[i]=max(r[i+1]+x[i],x[i]);for(R int i=n-1;i>=1;i--)r[i]=max(r[i+1],r[i]);for(R int i=2;i<n;i++)ans=max(ans,r[i+1]+l[i-1]);printf("%d",ans);
}

轉載于:https://www.cnblogs.com/-guz/p/9843807.html

總結

以上是生活随笔為你收集整理的简单DP【p2642】双子序列最大和的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。