UESTC OJ 1357 柱爷与最大区间和 - dblank

UESTC OJ 1357 柱爷与最大区间和

柱爷爱思考,凡事喜欢举一反三,常常能想到别人没想过的问题。

比如最大区间和这个问题:在一数列上选出一段区间,使得这段区间和最大。

柱爷想:如果选出两段区间(不相邻)会怎样呢?

柱爷很快想到了答案,你呢?
Input
第一行输入一个数NN,表示数组的长度。

第二行输入NN个数,表示各元素的值。

数据保证:

3≤N≤5000003≤N≤500000
−100<Ai<100−100<Ai<100
Output
输出一个数,表示数组的两段区间(不相邻)之和的最大值。

思路:我们可以先做俩次dp,求出以a[i]结尾的最大连续子序列和,和以a[i]开头的最大连续子序列和,然后前缀最大值和后缀最大值优化一下,然后枚举断点,就可以更新出最大值。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 1e3 + 10, Mod = 100000007;
typedef long long ll;
int a[NN], dp[NN], max1[NN], max2[NN];
int main()
{
    int n;
    while(cin>>n)
    {
        int sum = 0;
        for(int i = 1; i<=n; i++)
            scanf("%d", &a[i]), sum += a[i];
        memset(dp, 0, sizeof(dp));
        max1[0] = -inf;
        for(int i = 1; i<=n; i++)
        {
            dp[i] = max(dp[i-1] + a[i], a[i]);
            max1[i] = max(max1[i-1], dp[i]);
        }
        memset(dp, 0, sizeof(dp));
        max2[n+1] = -inf;
        for(int i = n; i>=1; i--)
        {
            dp[i] = max(dp[i+1] + a[i], a[i]);
            max2[i] = max(dp[i], max2[i+1]);
        }
        int ans = -inf;
        for(int i = 2; i<n; i++)
        {
            ans = max(max1[i-1] + max2[i+1], ans);
        }
        printf("%dn", ans);
    }
    return 0;
}

 

相关文章

发表新评论