【dp】P2642 双子序列最大和

题目描述

给定一个长度为n的整数序列，要求从中选出两个连续子序列，使得这两个连续子序列的序列和之和最大，最终只需输出最大和。一个连续子序列的和为该子序列中所有数之和。每个连续子序列的最小长度为1，并且两个连续子序列之间至少间隔一个数。

输入输出格式

输入格式：

第一行是一个整数表示n。

第二行是n个整数表示整数序列。

输出格式：

一个数，两个连续子序列的序列和之和。

输入输出样例

输入样例#1： 

5
83 223 -13 1331 -935

输出样例#1： 

1637

输入样例#2： 

3
83 223 -13

输出样例#2： 

70

说明

对于30%的数据N<=100。

对于60%的数据有N<=10000。

对于100%的数据有N<=1000000。

数据保证运算过程不会超过long long（int64）。

【思路】：

从左到右跑最一遍，从左到右跑一边，然后枚举分割点（注意要至少相隔1个）

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<string>
#include<cstring>
#define LL long long int
using namespace std;
const int maxn=999999999;
const int minn=-999999999;
inline int read() {
    char c = getchar();
    int x = 0, f = 1;
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
LL n,a[1000005],f1[10000005],s;
LL f2[1000005];
int main() {
    cin>>n;
    for(int i=1; i<=n; ++i) {
        a[i]=read();
    }
    int b_flag=1,e_flag=1,b,e;
    f1[1]=s=a[1];
    for(int i=2; i<=n; ++i) {
        s=max(a[i],s+a[i]);
        f1[i]=max(f1[i-1],s);
    }
    f2[n]=s=a[n];
    for(int i=n-1; i>=1; --i) {
        s=max(a[i],s+a[i]);
        f2[i]=max(f2[i+1],s);
    }
    LL ans=a[1]+a[3];
    for(int i=2; i<n; ++i) {
        ans=max(ans,f1[i-1]+f2[i+1]);
    }
    cout<<ans;
}