环线 题解

题目分析

这道题描述的是一个环形地铁线路，共有 $n$ 个车站，从车站 $i$ 只能前往车站 $i+1$（$n$ 的下一个是 $1$）。小 A 选择一个起点和一个终点，沿固定方向乘车，不能重复经过同一个车站。每经过一个车站会获得对应的快乐值 $a_i$（可能为负数）。我们需要选择一段行程，使得经过车站的快乐值总和最大。

由于不能重复经过车站，行程在环上一定是一段长度不超过 $n$ 的连续区间：

• 如果起点和终点相同，只经过一个车站，长度为 $1$。
• 如果乘车经过若干站，最多可以经过所有 $n$ 个站各一次（例如从 $1$ 出发到 $n$ 结束，或从 $2$ 出发到 $1$ 结束），此时长度为 $n$。

题目要求至少经过一个车站，因此子段不能为空，长度在 $1$ 到 $n$ 之间。

综上，问题转化为：在一个长度为 $n$ 的环形数组中，找一个长度不超过 $n$ 的非空连续子段，使得子段和最大。

解题思路

环形问题常见的处理方法是 破环成链：将原数组复制一份接在后面，得到长度为 $2n$ 的数组，这样环上任意一段长度不超过 $n$ 的连续子段都可以在复制后的数组中找到一段对应的连续区间。

设复制后数组为 $a[1 \dots 2n]$，前缀和为 $pre[i] = \sum_{j=1}^i a[j]$。
区间 $[l, r]$ 的和可以表示为 $pre[r] - pre[l-1]$。
我们要在满足 $r - l + 1 \le n$（即 $l \ge r - n + 1$）的条件下，最大化 $pre[r] - pre[l-1]$。

换个视角，对于每个右端点 $r$，我们需要找到一个对应的左端点 $L = l-1$，满足 $L \in [r - n,\ r - 1]$，并且 $pre[L]$ 尽可能小。那么以 $r$ 结尾的最大子段和就是 $pre[r] - \min\limits_{L \in [r-n,\ r-1]} pre[L]$。对所有 $r \in [1, 2n]$ 求最大值即可。

这个“滑动窗口求最小值”的问题，可以用单调队列在线性时间内解决。

算法说明

1. 数据扩展
   将 $a[1 \dots n]$ 复制到 $a[n+1 \dots 2n]$，使数组长度变为 $2n$。

2. 前缀和
   计算前缀和 $pre[1 \dots 2n]$，其中 $pre[0] = 0$ 但实际下标从 $1$ 开始，$pre[0]$ 可以隐式地认为是 $0$。为了统一处理，我们可以让队列初始包含位置 $0$。

3. 单调队列维护最小前缀和

   • 队列中存储候选左端点位置 $L$，并保证队列中对应的 $pre$ 值单调递增（队首为最小值）。
   • 遍历右端点 $r$ 从 $1$ 到 $2n$：
     • 移除队首已经“过期”的位置，即 $L<r-n$ 的元素。
     • 此时队首即为当前窗口 $[r-n, r-1]$ 中最小的 $pre$ 值对应的位置，用 $pre[r] - pre[队首]$ 更新答案。
     • 将当前 $r$ 加入队列前，从队尾弹出所有 $pre$ 值大于等于 $pre[r]$ 的位置，保持队列单调性。
   • 由于需要允许左端点 $L=0$（表示从第一个车站开始的情况），可以将 $0$ 预先入队，或者将队列初始化为包含位置 $0$。参考代码中的实现方式是将 ql=qr=1 且初始入队的是 $i=0$ 时的情况吗？让我们结合代码分析。

   参考代码里：

   • ql = qr = 1，但 q 数组并没有显式地在循环前放入初始值 $0$。它在循环中处理 ans = max(ans, pre[i] - pre[q[ql]])，当 $i=1$ 时，队列里能不能保证有元素？实际上代码中 q[ql] 的初始值是未定义的。但仔细看参考代码：在进入循环前，并没有给 q[1] 赋初始值，这看起来有潜在问题。实际上，为了正确处理从第一个车站开始的情况，我们应该在循环前让队列包含 $0$。标准写法是 q[++qr] = 0。参考代码可能是省略了或者默认为 $0$（取决于全局数组初始化为 $0$）。由于题目提供的代码是参考，我们可以在题解中补充正确的逻辑：将 $0$ 提前入队。

   我们以更稳健的方式描述：初始化时令 $q[1] = 0$，代表空前缀和 $pre[0] = 0$。然后 $r$ 从 $1$ 到 $2n$ 进行滑动。

4. 获得答案
   遍历结束后，ans 即为所求的最大快乐值。

时间复杂度分析

• 复制数组和计算前缀和：$O(n)$。
• 单调队列滑动窗口：每个位置最多入队、出队一次，也是 $O(n)$。
• 总时间复杂度：$O(n)$，空间复杂度 $O(n)$，完美应对 $n \le 2\times 10^5$ 的数据范围。

参考代码及解释

cpp
复制
1#include <cstdio>
2#include <algorithm>
3using namespace std;
4
5const int N = 4e5 + 5;      // 2n 的最大长度
6
7int n;
8long long a[N], pre[N];     // 原数组与前缀和
9int q[N], ql, qr;           // 单调队列，队首 ql，队尾 qr
10long long ans;
11
12int main() {
13    scanf("%d", &n);
14    for (int i = 1; i <= n; i++) {
15        scanf("%lld", &a[i]);
16    }
17    // 破环成链：复制数组到 2n
18    for (int i = n + 1; i <= 2 * n; i++) {
19        a[i] = a[i - n];
20    }
21    // 计算前缀和
22    for (int i = 1; i <= 2 * n; i++) {
23        pre[i] = pre[i - 1] + a[i];
24    }
25
26    // 单调队列初始化
27    ql = 1, qr = 0;         // 初始为空
28    q[++qr] = 0;            // 将位置 0（前缀和 0）入队
29    ans = -1e18;            // 答案初始化为极小值
30
31    // 滑动窗口，右端点从 1 到 2n
32    for (int i = 1; i <= 2 * n; i++) {
33        // 删除窗口外的元素（左端点 < i - n）
34        while (ql <= qr && q[ql] < i - n) {
35            ql++;
36        }
37        // 用当前窗口最小值更新答案
38        ans = max(ans, pre[i] - pre[q[ql]]);
39        // 维护队列单调性（递增），将当前 i 插入
40        while (ql <= qr && pre[q[qr]] >= pre[i]) {
41            qr--;
42        }
43        q[++qr] = i;
44    }
45
46    printf("%lld\n", ans);
47    return 0;
48}

代码要点解析：

• 破环成链：将原数组 $a[1..n]$ 复制到 $a[n+1..2n]$，使得任何长度不超过 $n$ 的环上子段都能表示为新数组中一个长度为 $L \le n$ 的连续段。
• 前缀和：pre[i] 表示前 $i$ 个数的和，区间和可以快速相减得到。
• 单调队列：
  • 队列存储的是位置下标，对应 pre 值保持 单调递增，这样队首始终是窗口内 pre 最小的位置。
  • q[ql] < i - n 判断队首是否超出窗口左界，超过则弹出。
  • 更新答案后，把当前右端点 $i$ 插入队列，为了保持单调性，从队尾弹出所有 pre 值大于等于 pre[i] 的位置。
• 答案初始化：由于快乐值可能全为负（$-10^9 \le a_i \le 10^9$），需要初始化为一个足够小的数，如 -1e18。
• 队列初值：入队 $0$ 是为了正确处理从第一个车站开始且左端点为 $0$ 的情况，这样 pre[1] - pre[0] 对应只选第一个车站的子段。

拓展思考

另一种常见解法是：非空环状最大子段和也可以分两种情况讨论：

1. 最大子段不跨越环的“接缝”，等价于普通的最大子段和。
2. 最大子段跨越接缝，等价于 总和减掉最小子段和（最小子段需要非空且不能等于全集，即长度至少为 $1$ 且至多为 $n-1$）。

最终答案取两种情况的最大值。这种方法也可以做到 $O(n)$，但需要处理全负等边界细节。本题的单调队列方法更加直观，且无论正负都能正确求解。

希望这篇题解对你有帮助，祝学习愉快！