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
#include
#include
#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