小猴编程周赛C++ | 环形最大子段和

学习C++从娃娃抓起！记录下在学而思小猴编程学习过程中的题目，记录每一个瞬间。侵权即删，谢谢支持！

附上汇总贴：小猴编程C++ | 汇总-CSDN博客

【题目描述】
给出一个长度为n的环形数组 a 1 , a 2 , … , a n a_1,a_2,\dots,a_n a1​,a2​,…,an​，其中 a 1 a_1 a1​和 a n a_n an​首尾相接， a n a_n an​相邻的下一个元素是 a 1 a_1 a1​， a 1 a_1 a1​相邻的上一个元素是 a n a_n an​。现在我们想在环形数组 a 1 , a 2 , … , a n a_1,a_2,\dots,a_n a1​,a2​,…,an​取连续且非空的一段，那么这段的和最大是多少？
【输入】
第一行，一个整数n；
第二行，n个整数 a 1 , a 2 , … , a n a_1,a_2,\dots,a_n a1​,a2​,…,an​。
【输出】
一行，一个整数，表示结果。
【输入样例】

4
1 -2 3 -2

【输出样例】

3

【代码详解】

#include <bits/stdc++.h>
using namespace std;
int n, a[200005], s[200005], minn=2e9, maxn=-2e9;
int mins[200005], maxs[200005];
int main()
{
    cin >> n;
    for (int i=1; i<=n; i++) {
        cin >> a[i];
        s[i] = s[i-1] + a[i];  // 求出前缀和数组
        mins[i] = min(mins[i-1], s[i]);  // 同步求出i项及以前的最小前缀和
        maxs[i] = max(maxs[i-1], s[i]);  // 同步求出i项及以前的最大前缀和
    }

    for (int j=1; j<=n; j++) {  // 遍历j，取消遍历i
        minn = min(minn, s[j]-maxs[j-1]);  // 普通线性队列最小子段和
        maxn = max(maxn, s[j]-mins[j-1]);  // 普通线性队列最大子段和
    }
    if (s[n]-minn==0) cout << maxn << endl;  // 特判，minn==s[n]时，如-1,-2,-3,-4，maxn应为-1，而不是0
    else cout << max(maxn, s[n]-minn) << endl;  // 否则正常输出
    return 0;
}

【运行结果】

4
1 -2 3 -2
3