Maximum sum

题目描述

给定长度为 $n$ （ $2 \leqslant n \leqslant 50000$ ）的整数序列，求两个不重合连续子段的和的最大值。 $T$ 组数据。

思路

两段不相交等价于存在分界 $k$ ，左段落在 $a[1..k]$ ，右段落在 $a[k+1..n]$ 。正向求前缀最大子段和 $g[k]$ ，反向求后缀最大子段和 $h[k+1]$ ，答案为 $\max_{1 \leqslant k < n}(g[k] + h[k+1])$ 。

参考代码

Python 版：

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 04:10
# update_at: 2026-09-30 04:10

import sys
from itertools import accumulate


def max_two_segments(a: list[int]) -> int:
    """求两个不重合连续子段之和的最大值（子段不交，且各至少一个元素）。"""
    # f[i]：右端点恰为 i 的最大子段和 —— 要么单取 a[i]，要么接在 f[i-1] 后面
    f = list(accumulate(a, lambda best, x: max(x, best + x)))

    # g[i]：在 a[0..i] 里任取一段的最大子段和，即前缀最大值
    g = list(accumulate(f, max))

    # h[i]：左端点恰为 i 的最大子段和，反向递推
    h = list(accumulate(reversed(a), lambda best, x: max(x, best + x)))
    h.reverse()

    # 枚举右段左端点 s，左段在 s 前面任取：ans = max(g[s-1] + h[s])
    return max(g[i] + h[i + 1] for i in range(len(a) - 1))


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    T = next(data)  # 测试组数

    for _ in range(T):
        n = next(data)
        a = [next(data) for _ in range(n)]  # 题面的 a_1..a_n
        out.append(str(max_two_segments(a)))

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2025-07-16 12:00
 * update_at: 2026-10-05 08:49
 */
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 50005;

ll a[MAXN];     // 原序列
ll f[MAXN];     // f[i]：右端点恰为 i 的最大子段和
ll g[MAXN];     // g[i]：a[1..i] 中的最大子段和（f 的前缀最大值）
ll h[MAXN];     // h[i]：左端点恰为 i 的最大子段和

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; ++i) cin >> a[i];

        // 正向：f[i] = max(a[i], f[i-1] + a[i])；g[i] = max(g[i-1], f[i])
        f[1] = a[1];
        g[1] = a[1];
        for (int i = 2; i <= n; ++i) {
            f[i] = max(a[i], f[i - 1] + a[i]);
            g[i] = max(g[i - 1], f[i]);
        }

        // 反向：h[i] = max(a[i], h[i+1] + a[i])
        h[n] = a[n];
        for (int i = n - 1; i >= 1; --i) {
            h[i] = max(a[i], h[i + 1] + a[i]);
        }

        // 枚举分界 k：左段在 [1,k]，右段从 k+1 开始
        ll ans = a[1] + a[2];
        for (int k = 1; k < n; ++k) {
            ans = max(ans, g[k] + h[k + 1]);
        }

        cout << ans << '\n';
    }
    return 0;
}

目录

题目描述

思路

参考代码