题目描述

Alice 和 Bob 又在玩一种新的纸牌游戏。这次的规则如下：桌上有 $n$ 张牌排成一行，第 $i$ 张牌的点数为 $a_i$。

首先，Alice 选择一个非空的连续牌段 $[l, r]$（$l \le r$）。随后，Bob 从这个牌段中移除一张牌 $j$（$l \le j \le r$）。游戏的得分为剩下牌段上所有牌的点数之和（即 $a_l + a_{l+1} + \dots + a_{j-1} + a_{j+1} + \dots + a_r$）。特别地，如果 Alice 选择的牌段只有一张牌，那么 Bob 移除这唯一的一张牌后，得分为 $0$。

Alice 希望让得分尽可能大，而 Bob 会选择让得分尽可能小的那张牌移除。

Alice 应该选择哪一段牌，使得最终得分最大？请输出最大得分。

输入格式

第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示牌的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$-30 \le a_i \le 30$），表示每张牌上的点数。

输出格式

输出一个整数，表示游戏的最终得分。

输入输出样例 #1

输入 #1

5
5 -2 10 -1 4

输出 #1

6

输入输出样例 #2

输入 #2

8
5 2 5 3 -30 -30 6 9

输出 #2

10

输入输出样例 #3

输入 #3

3
-10 6 -15

输出 #3

0

说明/提示

在第一个样例中，Alice 选择整个区间 $[1,5]$。Bob 从中移除第 $3$ 张牌，点数为 $10$。因此最终得分为 $5 + (-2) + (-1) + 4 = 6$。

在第二个样例中，Alice 选择区间 $[1,4]$，Bob 移除第 $1$ 张或第 $3$ 张牌，点数为 $5$，最终得分为 $5 + 2 + 3 = 10$。

在第三个样例中，Alice 可以选择任意一个长度为 $1$ 的区间：$[1,1]$、$[2,2]$ 或 $[3,3]$。Bob 移除唯一的一张牌后，得分为 $0$。如果 Alice 选择其他长度的区间，得分会小于 $0$。

第一步：形式化题意

题目规则是：

• Alice 选一个非空连续段 $[l,r]$
• Bob 从段里删掉一个位置 $j$
• 得分 = 段内剩余元素和（被删掉那个不算）

因为段内总和是固定的 $S=\sum_{i=l}^r a_i$，删掉 $a_j$ 后得分是：

$$S - a_j$$

Bob 想让得分尽量小 $⇒$ 让 $S-a_j$ 最小 $⇒$ 让 $a_j$ 尽量大。

所以 Bob 一定会删掉该段里的 最大值：

$$\text{score}([l,r]) = \sum_{i=l}^r a_i - \max_{i\in[l,r]} a_i $$

于是题目变成：

求所有子数组的 $\text{sum} - \text{max}$ 的最大值。
另外长度为 $1$ 时得分为 $0$，所以答案至少是 $0$。

第二步：解题

解法一：暴力解法

使用 $O(n^3)$ 的时间复杂度暴力枚举 $l, r$ ，求：

$$\text{score}([l,r]) = \sum_{i=l}^r a_i - \max_{i\in[l,r]} a_i $$

即可。

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10, inf = 1e9 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, a[N];
inline void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int Ans = -inf;
    for (int l = 1; l <= n; l++) {
        for (int r = l; r <= n; r++) {
            int Sum = 0, Mx = -inf;
            for (int i = l; i <= r; i++) {
                Sum += a[i];
                Mx = max(Mx, a[i]);
            }
            Ans = max(Ans, Sum - Mx);
        }
    }
    printf("%d\n", Ans);
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

解法二：暴力简单优化

可以发现没有比赛每次确认 $l, r$ 之后再去求一遍区间信息，只需要固定 $l$ ，然后让 $r$ 从 $l$ 开始往后跑，每次更新信息就可以了，因为该问题是连续子数组，只需要维护右边多出来的信息即可。

时间复杂度 $O(n^2)$ 。

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10, inf = 1e9 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, a[N];
inline void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int Ans = -inf;
    for (int l = 1; l <= n; l++) {
        int Sum = 0, Mx = -inf;
        for (int r = l; r <= n; r++) {
            Sum += a[r];
            Mx = max(Mx, a[r]);
            Ans = max(Ans, Sum - Mx);
        }
    }
    printf("%d\n", Ans);
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

解法三：值域优化 + 线性DP

可以观察到 $-30 \le a_i \le 30$ ，值域非常的小，从这里可以观察到 $\max_{i\in[l,r]} a_i$ 的选择也只有 $61$ 种。

那么就可以把问题拆成 $61$ 次 Kadane 风格 扫描：

$$\max_{[l,r]} \big(\text{sum}(l,r) - \max(l,r)\big) $$

具体优化思路：枚举子数组最大值 $\text{mx}$

固定最大值为 $\text{mx}$，那么合法子数组满足：

• 子数组内所有数 $\le \text{mx}$ (否则最大值会更大）
• 子数组内至少出现一次 $\text{mx}$ （否则最大值更小）

在这些子数组里需要最大化：

$$\text{sum} - \text{mx}$$

所以对固定 $\text{mx}$，等价于在满足条件的子数组中最大化 $\text{sum}$，最后减去 $\text{mx}$ 。

具体的 Kadane 可以直接使用贪心的策略进行扫描：

从左到右扫，遇到 $a_i > \text{mx}$ 直接断开（子数组不能跨过它）。
维护两个 以 $i$ 结尾 的最优值：

• $dp0$ 全都 $\le \text{mx}$ ，但 还没出现 $\text{mx}$ 的最大子段和
• $dp1$ 全都 $\le \text{mx}$ ，且 已经出现过 $\text{mx}$ 的最大子段和

转移（设 $x = a_i$）：

• 若 $x > \text{mx}$ 断开：$dp0 = dp1 = -inf$
• 若 $x == \text{mx}$ 现在一定 已经出现 $\max$ ：$dp1 = \max(dp1, dp0, 0) + x; dp0 = -inf$
• 若 $x < \text{mx}$ ：$dp0 = \max(dp0 + x, x); dp1 = dp1 + x$ （前提 $dp1$ 不是 $-inf$）

在转移的过程中不断的求 $dp1 - \text{mx}$ 更新答案。

时间复杂度：$O(61n)$

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10, inf = 1e9 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, a[N];
inline void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int Ans = -inf;
    for (int Mx = -30; Mx <= 30; Mx++) {
        int dp0 = -inf, dp1 = -inf;
        for (int i = 1; i <= n; i++) {
            int x = a[i];
            if (x > Mx) {
                dp0 = dp1 = -inf;
                continue;
            }
            if (x == Mx) {
                dp1 = max(dp1, max(dp0, 0)) + x;
                dp0 = -inf;
            }
            if (x < Mx) {
                dp0 = max(dp0, 0) + x;
                if (dp1 != -inf) dp1 += x;
            }
            if (dp1 != -inf) Ans = max(Ans, dp1 - Mx);
        }
    }
    printf("%d\n", Ans);
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

事实上根据题目可得长度为 $1$ 时得分为 $0$，所以答案至少是 $0$，所以枚举范围设置为 $[0, 30]$ 即可。

时间复杂度：$O(31n)$ 。

通过这个结论

• 子数组内所有数 $\le \text{mx}$ (否则最大值会更大）
• 子数组内至少出现一次 $\text{mx}$ （否则最大值更小）

也可以这样写：

• $x > \text{mx}$ 直接重新开始选。
• $Sum < 0$ 一样从新开始选，Kadane 的贪心策略。

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, a[N];
inline void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int Ans = 0;
    for (int Mx = 0; Mx <= 30; Mx++) {
        int Sum = 0;
        for (int i = 1; i <= n; i++) {
            Sum += a[i];
            if (a[i] > Mx) Sum = 0;
            if (Sum < 0) Sum = 0;
            Ans = max(Ans, Sum - Mx);
        }
    }
    printf("%d\n", Ans);
}
int main() {
    int _ = 1; 
    while (_--) solve();
    return 0;
}

解法四：单调栈 + 前缀和 + ST表

总结：

枚举被 Bob 删掉的 最大值位置 $i$ ，把答案拆成 $i$ 左边能吃到的最大连续和 + $i$ 右边能吃到的最大连续和；
但左右扩展都不能跨过 比 $a_i$ 更大的元素 ，这个边界用单调栈求；
左右那两段 最大连续和 用 前缀和 + ST 表（RMQ 查询区间最大前缀和） 快速算出来。

具体分析：

1）为什么能枚举被删除的最大值位置 $i$

就像前面说的题目等价于对任意子数组 $[l,r]$ 得分：

$$\text{score}(l,r)=\sum_{k=l}^{r} a_k - \max_{k\in[l,r]} a_k $$

因为 Bob 会删掉最大值（删哪个都行，但值一定是最大值）。

如果 假设 最大值删掉的是位置 $i$（也就是这个子数组的最大值是 $a_i$），那么删掉以后剩下的和就是：

$$\sum_{k=l}^{i-1} a_k + \sum_{k=i+1}^{r} a_k$$

也就是：$i$ 左边紧贴着 $i$ 的一段连续和 + $i$ 右边紧贴着 $i$ 的一段连续和。

所以对固定 $i$，最大化：

• 左侧：选一个 $l$，让 $[l, i-1]$ 连续且和尽量大
• 右侧：选一个 $r$，让 $[i+1, r]$ 连续且和尽量大

最后把左右相加，就是 删掉 $i$ 后能得到的最大分数 。

2）为什么左右不能随便扩：必须卡在下一次更大元素边界内

要让 $a_i$ 真的是整个 $[l,r]$ 的最大值，区间里 不能出现 $> a_i$ 的数。

所以对每个位置 $i$，定义：

• $r_i = i$ 右边第一个满足 $a_{r_i} > a_i$ 的位置（严格更大）
• 如果不存在，则 $r_i=n+1$

那么从 $i$ 往右，最多只能把子数组扩到 $r_i-1$，否则区间里出现更大的数，最大值就不是 $a_i$ 了。

同理，往左也有一个 左边第一个更大 ，通过 反转数组再做一次同样的 $r$ 来实现的（等价于求左边边界）。

3）单调栈怎么求 $r$（Next Greater Element）

在 build() 里这段：

while (top && a[q[top]] < a[i]) r[q[top]] = i, top--;
q[++top] = i;

维护一个 按值单调不增 的栈（栈里存下标）：

• 当新来的 $a_i$ 比栈顶更大，就说明 $i$ 是栈顶元素的 下一个严格更大元素，于是把 $r_{\text{栈顶}}=i$ 并弹出
• 最后栈里剩下的都没有更大元素，$r= n+1$

因此得到的 $r_i$ 为：从 $i$ 往右第一个严格更大 的位置。

4）右侧最大连续和：用前缀和 + ST 表直接计算

固定 $i$，右侧要：

$$\max_{x \in [i,, r[i)-1]} \sum_{k=i+1}^{x} a_k$$

用前缀和 $pre[t]=a[1]+...+a[t]$，有：

$$\sum_{k=i+1}^{x} a_k = pre[x] - pre[i]$$

所以右侧最大值就是：

$$\max_{x\in[i, r[i)-1]} (pre[x]) - pre[i]$$

代码就是：

t1 = s1.query(p1, s1.r[p1] - 1) - s1.pre[p1];

其中：

• $s1.query(l,r)$ 返回 $max(pre[l..r])$（ST 表 RMQ）
• 减去 $pre[p1]$ 就得到最大 $pre[x]-pre[p1]$

5）左侧最大连续和：反转数组再来一遍

左侧我们要：

$$\max_{l \in [L, i]} \sum_{k=l}^{i-1} a_k$$

这和 从某点往右取最大连续和 是对称的。用技巧：

• 把数组反转
• 在反转数组里，同样计算 从 $p2$ 往右能取到的最大连续和

因此：

reverse(a + 1, a + n + 1);
s2.build(a);

然后对原来的 $i$，它在反转数组的位置是：

p2 = n - p1 + 1;

于是左侧贡献就变成：

t2 = s2.query(p2, s2.r[p2] - 1) - s2.pre[p2];

6）为什么答案是 $t1 + t2$

对固定 $i$：

• $t2$ = 左侧能取到的最佳连续和（不含 $i$）
• $t1$ = 右侧能取到的最佳连续和（不含 $i$）

那么把它们拼起来得到的子数组就是：

$$[l, i-1] \cup {i} \cup [i+1, r]$$

也就是某个包含 $i$ 的连续区间 $[l,r]$，并且由于左右都不跨过更大元素，区间里不会出现 $> a_i$，所以 $a_i$ 确实可作为最大值（允许相等最大值存在也没问题）。

因此：

Ans = max(Ans, t1 + t2);

枚举所有 $i$ 取最大，就是全局最优。

7）复杂度

• 单调栈求 $r$：$O(n)$
• ST 表建表：$O(n\log n)$
• 每个 $i$ 两次 RMQ：$O(1)$，共 $O(n)$

总复杂度： $O(n\log n)$ 。

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 2e5 + 10, inf = 1e9 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, a[N], LG[N];
struct node{
    int pre[N], st[N][30], r[N], q[N];
    int query(int l, int r){
        int len = LG[r - l + 1];
        return max(st[l][len], st[r - (1 << len) + 1][len]);
    }
    void build(int *a){
        memset(pre, 0, sizeof(pre));
        for (int i = 1; i <= n; i++) {
            pre[i] = st[i][0] = pre[i - 1] + a[i];
        }
        for (int j = 1; j <= 19; j++) {
            for (int i = 1; i + (1 << (j - 1)) <= n; i++) {
                st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
            }
        }
        int top = 0;
        for (int i = 1; i <= n; i++) {
            while (top && a[q[top]] < a[i]) r[q[top]] = i, top--;
            q[++top] = i;
        }
        for (int i = 1; i <= top; i++) {
            r[q[i]] = n + 1;
        }
    }
}s1, s2;
inline void solve() {
    cin >> n;
    LG[0] = -1;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        LG[i] = LG[i / 2] + 1;
    }
    s1.build(a);
    reverse(a + 1, a + n + 1);
    s2.build(a);
    int Ans = -inf;
    for (int i = 1; i <= n; i++) {
        int p1 = i, p2 = n - p1 + 1;
        int t1 = s1.query(p1, s1.r[p1] - 1) - s1.pre[p1], t2 = s2.query(p2, s2.r[p2] - 1) - s2.pre[p2];
        Ans = max(Ans, t1 + t2);
    }
    printf("%d\n", Ans);
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

解法五：线段树

和 单调栈 + 前缀和 + ST表 的解法本质一致，只是把 ST表 换成了 线段树 。

总结下来其实就是：

• 单调栈把 合法扩展范围 卡在 最近严格更大元素之间；
• 前缀和把 最大连续段和 转成 某段前缀和的 $\min/\max$ 差；
• 线段树提供 $\min(pre) / \max(pre)$ 的区间查询，于是每个 $i$ 在 $O(logn)$ 算出 $left+right$ 。

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n;
LL a[N], pre[N];
struct Seg {
    LL n, sz;
    vector<LL> mn, mx;
    void init(int _n) {
        n = _n;
        sz = 1;
        while (sz < n) sz <<= 1;
        mn.assign(sz << 1, (LL)4e18);
        mx.assign(sz << 1, (LL)-4e18);
    }
    void build(const vector<LL> &b) {
        for (int i = 0; i < n; i++) {
            mn[sz + i] = mx[sz + i] = b[i];
        }
        for (int i = sz - 1; i >= 1; i--) {
            mn[i] = min(mn[i << 1], mn[i << 1 | 1]);
            mx[i] = max(mx[i << 1], mx[i << 1 | 1]);
        }
    }
    LL qmin(int l, int r) {
        LL res = (LL)4e18;
        l += sz; r += sz;
        while (l <= r) {
            if (l & 1) res = min(res, mn[l++]);
            if (!(r & 1)) res = min(res, mn[r--]);
            l >>= 1; r >>= 1;
        }
        return res;
    }
    LL qmax(int l, int r) {
        LL res = (LL)-4e18;
        l += sz; r += sz;
        while (l <= r) {
            if (l & 1) res = max(res, mx[l++]);
            if (!(r & 1)) res = max(res, mx[r--]);
            l >>= 1; r >>= 1;
        }
        return res;
    }
};
inline void solve() {
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    // 前缀和 pre[0..n]
    pre[0] = 0;
    for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + a[i];
    // 单调栈求 pg/ng（严格更大）
    int pg[N], ng[N], st[N];
    int top = 0;
    // pg
    top = 0;
    for (int i = 1; i <= n; i++) {
        while (top && a[st[top]] <= a[i]) top--;
        pg[i] = top ? st[top] : 0;
        st[++top] = i;
    }
    // ng
    top = 0;
    for (int i = n; i >= 1; i--) {
        while (top && a[st[top]] <= a[i]) top--;
        ng[i] = top ? st[top] : n + 1;
        st[++top] = i;
    }
    // 建线段树：维护 pre 的区间 min/max
    vector<LL> b(n + 1);
    for (int i = 0; i <= n; i++) b[i] = pre[i];
    Seg seg;
    seg.init(n + 1);
    seg.build(b);
    LL Ans = 0;
    for (int i = 1; i <= n; i++) {
        int L = pg[i] + 1;
        int R = ng[i] - 1;
        LL leftMin = seg.qmin(pg[i], i - 1);
        LL left = pre[i - 1] - leftMin;
        LL rightMax = seg.qmax(i, R);
        LL right = rightMax - pre[i];
        Ans = max(Ans, left + right);
    }
    printf("%lld\n", Ans);
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}