「一本通 5.5 例 2」最大连续和

题目描述

给定长度为 $n$ 的整数序列，找出一段连续且长度不超过 $m$ 的子段，使其和最大（ $1 \le n, m \le 2 \times 10^5$ ）。

思路

以 $i$ 结尾的最大子段和为 $S_i - \min S_j$ （ $j \in [i-m, i-1]$ ），用单调队列维护滑动窗口内前缀和最小值，队首过期弹出、队尾不小于当前值则淘汰，每个下标进出各一次，整体 $O(n)$ 。

参考代码

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#!/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 20:52
# update_at: 2026-09-30 20:52

import sys
from collections import deque

NEG = -10**12  # 前缀和绝对值不超过 2e8，哨兵足够小即可


def max_window_sum(pres: list[int], m: int) -> int:
    """长度不超过 m 的最大子段和：max(pres[i] - pres[j])，j ∈ [i-m, i-1]。"""
    dq: deque[int] = deque([0])  # 下标递增、前缀和递增；队首是当前最优左端点候选
    best = NEG
    for i in range(1, len(pres)):
        # 此刻队列只装下标 0..i-1，且队尾是 i-1（m >= 1），弹出后必不为空
        while dq[0] < i - m:  # 左端点滑出长度 m 的窗口
            dq.popleft()
        best = max(best, pres[i] - pres[dq[0]])  # 以 i 结尾、长度不超过 m 的最大和
        while dq and pres[dq[-1]] >= pres[i]:  # 维持递增：更小的前缀和对后面更有利（队列可能被清空）
            dq.pop()
        dq.append(i)
    return best


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)
    pres = [0]  # 前缀和：pres[i] = A_1..A_i 之和，pres[0] = 0
    for _ in range(n):
        pres.append(pres[-1] + next(data))
    print(max_window_sum(pres, m))


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/**
 * 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-10-06 01:04
 * update_at: 2026-10-06 01:04
 */

#include <cstdio>
#include <deque>
using namespace std;

typedef long long ll;

const int MAXN = 200005;

int n, m;
ll a[MAXN]; // a[i] 表示第 i 个数
ll s[MAXN]; // s[i] 表示前缀和 A_1 + ... + A_i，s[0] = 0

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        s[i] = s[i - 1] + a[i];
    }

    // 以 i 结尾、长度不超过 m 的子段和 = s[i] - s[j]，j ∈ [i-m, i-1]，
    // 即用单调队列维护窗口 [i-m, i-1] 内最小的 s[j]
    deque<int> dq; // 队列装前缀和下标，下标递增、对应 s 值也递增，队首是窗口最小值
    dq.push_back(0);
    ll ans = s[1] - s[0]; // 长度为 1 的子段 A_1 至少存在（m >= 1）
    for (int i = 1; i <= n; i++) {
        // 弹出队首里已经滑出窗口的下标（j < i-m 时子段长度超过 m）
        while (!dq.empty() && dq.front() < i - m)
            dq.pop_front();

        // 此时窗口 [i-m, i-1] 内最小前缀和在队首，更新答案
        ll cur = s[i] - s[dq.front()];
        if (cur > ans)
            ans = cur;

        // 队尾淘汰：s 值不小于 s[i] 的下标以后永远当不了最小值，直接出队
        while (!dq.empty() && s[dq.back()] >= s[i])
            dq.pop_back();
        dq.push_back(i);
    }

    printf("%lld\n", ans);
    return 0;
}

「一本通 5.5 例 2」最大连续和

目录

题目描述

思路

参考代码