GESP 题解库 / 6 级题解 / [GESP202503 六级] 环线 · 第 9 / 27 题
GESP202503 六级 · P11963 · 中等

环线

环上选一段连续的弧(长度 1~n)使快乐值之和最大。

📊
n ≤ 2 × 10⁵
车站数量
🔢
long long
快乐值范围
⚡
O(n)
时间复杂度
🎯
环形最大子段和 + 单调队列
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

地铁环线有 n 个车站,站 i 的下一站是 i+1(站 n 的下一站是站 1)。小 A 从某站出发、到某站结束,至少经过一个车站,且不会重复经过同一车站。经过站 i 获得 aᵢ 点快乐值(可正可负)。求最大快乐值总和。

💡
人话翻译:由于只能"一路向前",行程就是环上的一段连续弧,长度可以是 1 ~ n(n = 从某站出发绕一整圈到它的前一站,每站只经过一次)。
所以这是经典的"环形最大子段和"问题。做法是把数组复制一倍 + 前缀和 + 单调队列,把"长度不超过 n 的最大子段和"在 O(n) 内求出。

🔍 关键词提取

环形最大子段和前缀和单调队列滑动窗口最小值

已知条件

项目说明
输入第一行 n;第二行 a₁…aₙ
输出最大快乐值总和
数据范围1 ≤ n ≤ 2 × 10⁵
快乐值−10⁹ ≤ aᵢ ≤ 10⁹(可为负)
行程环上连续弧,长度 1 ~ n

需要解决的问题

02
思维导图
整理解题思路的全貌
⭕ 环形最大子段和 = 前缀和 + 单调队列
🧠 模型
行程 = 环上连续弧
长度 ∈ [1, n]
求弧上元素和的最大值
经典"环形最大子段和"
🔧 复制一倍
把 a 复制成 2n 长度
任意弧都变成一段普通区间
再限定长度 ≤ n
避免分类讨论"跨环"
⚡ 单调队列
pre[i] 为前缀和
弧和 = pre[e] − pre[s]
固定 e,取窗口内最小 pre
队列维护递增的 pre
⚠️ 易错点
用 int(和可达 2 × 10¹⁴)
窗口大小写成 n+1 或 n−1
队列忘记弹出过期下标
n = 1 时特判
03
样例手算推导
两个样例的完整分析

🧮 样例 1:a = [−1, 2, 3, 0]

先把所有长度 ≤ 4 的弧列出来(环上连续)。

弧长候选弧(按环顺序)最大和
1[−1]、[2]、[3]、[0]3
2[−1,2]、[2,3]、[3,0]、[0,−1]5(2 + 3)
3[−1,2,3]、[2,3,0]、[3,0,−1]、[0,−1,2]5(2+3+0)
4[−1,2,3,0]4

最大 = 5 ✓(走车站 2 → 3)

🔑
注意长度 3 的 [2,3,0] 也是 5,与长度 2 的 [2,3] 并列最优。这说明最优方案不唯一,但答案唯一。
另外注意负值 −1:它被"绕开"了——因为我们是从车站 2 出发到车站 3,不必经过车站 1。

🧮 样例 2:a = [−3, 4, −5, 1, 3]

这组数据的最优解跨过了"环的连接处",正好体现环形问题的特点。

1
先看"不跨环"的最大弧

线性数组 [−3, 4, −5, 1, 3] 的最大子段:

[4] = 4;[1,3] = 4;[4,−5,1,3] = 3

所以不跨环的最优是 4

不跨环最优 4

2
再看"跨环"的弧

跨环意味着弧"绕过"了数组的首尾相接处

例如 [1, 3, −3, 4]:从站 4 出发 → 站 5 → 站 1 → 站 2

和 = 1 + 3 + (−3) + 4 = 5

这比 4 更好!

跨环可得 5

3
验证长度限制

该弧长 4 ≤ n = 5 ✓

有没有长度为 5 的弧?= 整圈 = −3+4−5+1+3 = 0

所以不能更长(长度 5 本身合法但和只有 0)

最优就是 5

✅ 答案 5

最优行程:站 4 → 5 → 1 → 2,快乐值 1 + 3 − 3 + 4 = 5 ✓

⚠️
这个样例是本类问题的"试金石":如果只做一维的普通最大子段和,会得到 4(而不是正确答案 5)——因为答案跨过了数组的"断点"。
复制一倍 + 限制窗口长度正是为了正确处理这种情况。
04
解法对比
单调队列 O(n) vs 枚举 O(n²)

⚔️ 解法对比

🟢 复制一倍 + 单调队列(推荐) 推荐

前缀和 + 滑动窗口最小值,一次 O(n) 扫描

  • 时间 O(n)
  • n = 2 × 10⁵ 时约 4 × 10⁵
  • 代码 25 行
  • 空间 O(n)
💡
核心等式:弧 [s+1, e] 的和 = pre[e] − pre[s]。固定 e,要最大化它就最小化 pre[s],而 s 的范围是 [e−n, e−1]。这就是"滑动窗口最小值",用单调队列 O(1) 摊还维护。

🟠 枚举起点终点

枚举所有弧,累加求和取最大

  • 时间 O(n²)
  • n = 2000 时可行(40% 测试点)
  • n = 2 × 10⁵ 时 4 × 10¹⁰
  • 必然超时
⚠️
注意数据分档:n ≤ 200 得 20%、n ≤ 2000 得 40%,但想满分必须 O(n)。看到"n ≤ 2 × 10⁵"就该意识到 O(n²) 不可行。

📈 性能对比

方案复杂度(n = 2 × 10⁵)可行性
单调队列约 4 × 10⁵✅ 稳过
枚举起点终点约 4 × 10¹⁰❌ 超时
05
算法流程图
复制一倍后用单调队列求最大子段和
开始读入 n 和数组 a;把 a 复制一倍得到长度 2n 的数组计算前缀和 pre[0..2n];pre[0] = 0ans = 负无穷;用单调队列 dq 存前缀和的下标(保持 pre 递增)e 从 1 遍历到 2n队首下标是否已经超出窗口 [e − n, e − 1]?是 ✓弹出队首否 ✗保持ans = max(ans, pre[e] − pre[队首]);然后维护单调性并压入 e输出 anse 加 1 继续扫描
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

⭕ 环线最大快乐值

输入一组快乐值,程序会用环形算法求出最大值,并与暴力枚举互相验证。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#include <bits/stdc++.h>
using namespace std;

long long a[400005], pre[400005];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
        a[i + n] = a[i];                  // 复制一倍
    }

    int N = 2 * n;
    pre[0] = 0;
    for (int i = 0; i < N; i++) pre[i + 1] = pre[i] + a[i];

    // 单调队列:存前缀和的下标,保持 pre 递增
    deque<int> dq;
    dq.push_back(0);
    long long ans = LLONG_MIN;

    for (int e = 1; e <= N; e++) {
        // 弹出超出窗口的下标(窗口是 [e - n, e - 1])
        while (!dq.empty() && dq.front() < e - n) dq.pop_front();

        // 用队首(窗口内最小的 pre)更新答案
        ans = max(ans, pre[e] - pre[dq.front()]);

        // 维护单调性后把 e 入队
        while (!dq.empty() && pre[dq.back()] >= pre[e]) dq.pop_back();
        dq.push_back(e);
    }

    printf("%lld\n", ans);
    return 0;
}
🔑
窗口为什么是 [e − n, e − 1]?e 是弧的右端点(在前缀和里是"第 e 个位置之后"),s 是左端点前一个位置。弧的长度 = e − s,要求 1 ≤ e − s ≤ n,所以 s ∈ [e − n, e − 1] ✓。
不同题目里"窗口长度"的定义容易搞混,建议先把长度约束写成 e − s 的不等式再推。

📖 关键几行怎么看

代码作用为什么这样写
a[i + n] = a[i]复制一倍把环形摊平成线性
pre[i + 1] = pre[i] + a[i]前缀和让区间和能 O(1) 求出
while (dq.front() < e - n) pop_front()窗口过期保证弧长 ≤ n
pre[e] - pre[dq.front()]更新答案队首是窗口内最小的 pre
while (... >= pre[e]) pop_back()维护单调保证队列里 pre 递增
⚠️
四个坑:① 用 int(和可达 2 × 10¹⁴);② 窗口边界写错(应该是 e − n,对应"弧长 ≤ n");③ 忘记"先更新答案再压入 e"的顺序(否则可能出现长度 0 的弧);④ ans 初值取 0(应为负无穷,因为答案可能是负数)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
4
-1 2 3 0
5题面样例 1(走站 2 → 3)
5
-3 4 -5 1 3
5题面样例 2(跨环)
1
7
7只有一个车站
1
-7
-7只有一个车站且为负,必须经过它
3
-1 -2 -3
-1全为负,取最大的单个
4
1 1 1 1
4全为正,绕一整圈(经过全部 4 站一次)
✅
自查清单:① 复制一倍了吗?② 窗口是 e−n 到 e−1 吗?③ ans 初值是负无穷吗?

🚨 易错点清单

⚠️
ans 初值取 0:答案可能是负数(如全负数组),初值应取负无穷。
⚠️
窗口边界错:要求弧长 ≤ n,对应 s ≥ e − n。
⚠️
用 int:和可达 2 × 10¹⁴,需要 long long。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n)
空间复杂度
O(n)
n 最大
2 × 10⁵
运算量
约 4 × 10⁵

时间怎么算的?

空间都用在哪?

需要存 2n 长度的数组与前缀和。

✅ 约 40 万次操作,瞬间完成。若只做一维 Kadane(不处理跨环),样例 2 会错答为 4。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 环形最大子段和:两种经典做法
// 做法 A(推荐):复制一倍 + 前缀和 + 单调队列(本题代码)
// 做法 B:分类讨论
//   ans = max(不跨环的最大子段和, 总和 − 不跨环的最小子段和)
//   注意:若"最小子段"就是整个数组,要特殊处理(对应"不能取空弧")

// 单调队列求滑动窗口最小值(通用模板)
deque<int> dq;
for (int i = 0; i < N; i++) {
    while (!dq.empty() && dq.front() < i - k + 1) dq.pop_front();  // 过期
    while (!dq.empty() && a[dq.back()] >= a[i]) dq.pop_back();     // 维护单调
    dq.push_back(i);
    // 此时 dq.front() 就是窗口 [i-k+1, i] 内最小值的下标
}

// 环形问题的通用思路
// 1. 复制一倍摊平成线性
// 2. 用"长度限制的滑动窗口"约束
// 3. 避免分类讨论"是否跨环"

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
环形 → 线性复制一倍所有环形区间问题
滑动窗口最小值单调队列 O(n)固定窗口长度的最值查询
前缀和 + 队列区间和转成前缀差子段和、区间统计类问题
🌟
思考题:如果题目改成"弧长恰好为 k"(必须经过恰好 k 个车站),代码要怎么改?(提示:更简单——窗口大小固定成 k 而不是 n,即把 e − n 改成 e − k。这说明单调队列框架非常灵活,窗口大小就是"约束条件"的直接映射。)