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

#include <bits/stdc++.h>

using namespace std;


// 最大连续和 + 最小连续和 = sum ,二者和一就是sum 
int main() {
   int n;
   cin >> n;
   vector<int> arr(n);
   for(int i = 0; i < n; i++) cin >> arr[i];
   int sum,dpmx,dpmn,mx,mn;
   sum = dpmx = dpmn = mx = mn = arr[0];

   for(int i = 1; i < n; i++){
    dpmx = max(dpmx+arr[i],arr[i]);
    dpmn = min(dpmn+arr[i],arr[i]);
    mx = max(dpmx,mx);
    mn = min(dpmn,mn);
    sum += arr[i];
   }
   if(mx < 0) { // 最大和都为负数! 双边都为负数! 
    cout << mx << endl;
    return 0;
   }
   
   if(mx + mn < sum) cout << sum - mn << endl; // 交接区域属于最大大连续和领域!
   else cout << mx << endl;  // 交界区域属于最小连续和领域! 
   return 0;
}
// 64 位输出请用 printf("%lld")