题目描述
小 A 喜欢坐地铁。地铁环线有 n n n 个车站，依次以 1 , 2 , ⋯ , n 1,2,\cdots,n 1,2,⋯,n 标号。车站 i ( 1 ≤ i < n ) i\ (1\leq i<n) i (1≤i<n) 的下一个车站是车站 i + 1 i+1 i+1。特殊地，车站 n n n 的下一个车站是车站 1 1 1。
小 A 会从某个车站出发，乘坐地铁环线到某个车站结束行程，这意味着小 A 至少会经过一个车站。小 A 不会经过一个车站多次。当小 A 乘坐地铁环线经过车站 i i i 时，小 A 会获得 a i a_i ai 点快乐值。请你安排小 A 的行程，选择出发车站与结束车站，使得获得的快乐值总和最大。
输入格式
第一行，一个正整数 n n n，表示车站的数量。
第二行， n n n 个整数 a i a_i ai，分别表示经过每个车站时获得的快乐值。
输出格式
一行，一个整数，表示小 A 能获得的最大快乐值。
输入输出样例 #1
输入 #1
4
-1 2 3 0
输出 #1
5
输入输出样例 #2
输入 #2
5
-3 4 -5 1 3
输出 #2
5
说明/提示
对于 20 % 20\% 20% 的测试点，保证 1 ≤ n ≤ 200 1\leq n\leq 200 1≤n≤200。
对于 40 % 40\% 40% 的测试点，保证 1 ≤ n ≤ 2000 1\leq n\leq 2000 1≤n≤2000。
对于所有测试点，保证 1 ≤ n ≤ 2 × 10 5 1\leq n\leq 2\times 10^5 1≤n≤2×105， − 10 9 ≤ a i ≤ 10 9 -10^9\leq a_i\leq 10^9 −109≤ai≤109。
solution
求区间和的最大值和最小值，区间和的最小值意味着互补区间的最大值，两者中更大的为结果
代码
#include <iostream>
#include "bit"
#include "vector"
#include "unordered_set"
#include "set"
#include "queue"
#include "algorithm"
#include "bitset"using namespace std;long long n, x, Min = 1e9, Max = -1e9, s, MMin = 2e9, MMax = -2e9;int main() {cin >> n;for (int i = 0; i < n; i++) {cin >> x;s += x;MMin = min(MMin, s - Max);MMax = max(MMax, s - Min);Min = min(Min, s);Max = max(Max, s);}cout << max(s - MMin, MMax);
}
结果
)
