2019 ICPC 南昌网络赛 I 单调栈 + 前缀和

发表于 | 分类于 | 阅读次数：

单调栈 + 前缀和

题目链接

题意

给你一个序列，每一段区间的值=这段区间的和*这段区间的最小值。现在让你求区间的最大值。

思路

我们枚举每个数字，以他为最小值进行左右延伸，假设这个数字是正数，那么就直接是左右延伸后的区间和*这个数字。如果这个数字是负数，那么我们需要让这个区间的和尽量的低，先把这个数字当做右边界求出这个数字的左边的值到这个数字的区间的和的最小值，在以这个数字为左边界，求出这个数字到这个数字右边的值的区间和的最小值，这样把这两个值相加就是这个负数为最小值的区间的最小的和，这样再乘以这个负数，就可以求出这段区间的最大值了。关键就是利用单调栈求出左右延伸的边界。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <queue>
#include <cstring>
#include <bitset>
#include <stack>
using namespace std;

typedef long long ll;
const int maxn = 500005;
const int inf = 0x3f3f3f3f;
struct node{
   ll value;
   int pos;
};
int n;
ll sum[maxn];
ll Max[maxn], Max1[maxn],a[maxn],L[maxn],R[maxn],Max2[maxn];
void solve()
{
    stack<node>S1,S2;
    for(int i = 1; i <= n; ++i)
    {
        while(!S1.empty() && S1.top().value >= a[i])
        {
            S1.pop();
        }
        if(S1.size() == 0) L[i] = 1;
        else L[i] = S1.top().pos + 1;
        S1.push({a[i],i});
    }
    for(int i = n; i >= 1; --i)
    {
        while(!S2.empty() && S2.top().value >= a[i]){
            S2.pop();
        }
        if(S2.size() == 0) R[i] = n;
        else R[i] = S2.top().pos - 1;
        S2.push({a[i], i});
    }
    for(int i = 1; i <= n; ++i)
    {
        if(a[i] >= 0) continue;
        for(int j = L[i]; j <= i; ++j)
        {
            Max[i] = min(Max[i], sum[i] - sum[j - 1]);
        }
        for(int j = i + 1; j <= R[i]; ++j)
        {
            Max1[i] = min(Max1[i] , sum[j] - sum[i]);
        }
        Max2[i] = Max[i] + Max1[i];
    }
    ll ans = -1;
    for(int i = 1; i <= n; ++i)
    {
        if(a[i] >= 0)
        {
            ans = max(ans, a[i] * (sum[R[i]] - sum[L[i]-1]));
        }
        else{
            ans = max(ans, a[i] * Max2[i]);
        }
    }
    cout << ans << '\n';
}
int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++i)
        {
            scanf("%lld",&a[i]);
            sum[i] = sum[i - 1] + a[i];
        }
    solve();
}