欢迎大家订阅我的CSDN专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总帖：GESP认证C++编程真题解析 | 汇总
【题目来源】
洛谷：[P11963 GESP202503 六级] 环线 - 洛谷
【题目描述】
小 A 喜欢坐地铁。地铁环线有 \(n\) 个车站，依次以 \(1,2,⋯,n\) 标号。车站 \(i (1≤i<n)\) 的下一个车站是车站 \(i+1\)。特殊地，车站 \(n\) 的下一个车站是车站 \(1\)。
小 A 会从某个车站出发，乘坐地铁环线到某个车站结束行程，这意味着小 A 至少会经过一个车站。小 A 不会经过一个车站多次。当小 A 乘坐地铁环线经过车站 \(i\) 时，小 A 会获得 \(a_i\) 点快乐值。请你安排小 A 的行程，选择出发车站与结束车站，使得获得的快乐值总和最大。
【输入】
第一行，一个正整数 \(n\)，表示车站的数量。
第二行，\(n\) 个整数 \(a_i\)，分别表示经过每个车站时获得的快乐值。
【输出】
一行，一个整数，表示小 A 能获得的最大快乐值。
【输入样例】
4
-1 2 3 0
【输出样例】
5
【算法标签】
《洛谷 P11963 环线》 #单调队列# #GESP# #2025#
【代码详解】
#include <bits/stdc++.h>
using namespace std;#define int long long // 定义宏，将int替换为long long类型
const int N = 200005; // 定义数组的最大大小
int n; // 输入的数字个数
int a[N * 2]; // 存储输入的数字，并复制一份实现环形处理
int sa[N * 2]; // 前缀和数组
int maxn = -2e18; // 记录最大子段和，初始化为极小值
int q[N * 2]; // 单调队列，用于维护窗口最小值signed main() {cin >> n; // 输入数字个数// 输入数字并复制一份实现环形处理for (int i = 1; i <= n; i++) {int x;cin >> x;a[i] = x;a[i + n] = x; // 复制一份，实现环形数组}// 计算前缀和数组for (int i = 1; i <= 2 * n; i++) {sa[i] = sa[i - 1] + a[i];}// 初始化单调队列int hh = 0, tt = -1; // 队列头尾指针// 遍历前缀和数组，寻找最大子段和for (int i = 1; i <= 2 * n; i++) {// 维护窗口大小不超过nwhile (hh <= tt && q[hh] < i - n) hh++;// 计算当前窗口的最大子段和if (hh <= tt) {maxn = max(maxn, sa[i] - sa[q[hh]]);}// 维护单调递增队列while (hh <= tt && sa[q[tt]] >= sa[i]) tt--;q[++tt] = i;}cout << maxn << endl; // 输出最大子段和return 0;
}
【运行结果】
4
-1 2 3 0
5