题解 | #环形数组的连续子数组最大和#

#include <iostream>using namespace std;

const int N = 100010;int a[N], f[N], g[N];int main() {int n;cin >> n;

for(int i = 0; i < n; i ++){
    cin >> a[i];
    f[i] = a[i];
    g[i] = a[i];
}    
int sum = a[0], minN = 0, maxN = a[0];
for(int i = 1; i < n; i ++){
    f[i] = max(f[i - 1] + a[i], a[i]);
    sum += a[i];
    if(f[i] > maxN) maxN = f[i]; 
}
// 找中间是否出现负数 因为如果数组全是正数 就不会经过环 在1 - n就是最大值了
// 所以要在 1 - n - 1寻找最小的包含负数的子数组
for(int i = 1; i < n - 1; i ++){
    g[i] = min(g[i - 1] + a[i], g[i]);
    if(g[i] < minN) minN = g[i];
}
int res = -1e9;
// 最后比较 在环内的数组大还是环外的大
res = max(sum - minN, maxN);
cout << res << endl;
return 0;

}