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

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin>>n;
    vector<int> arr(n,0);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    //求非环的连续最大值
    int current_maxValue=arr[0];
    int maxValue=arr[0];
    for(int i=1;i<n;i++){
        if(current_maxValue+arr[i]>arr[i]){
            current_maxValue+=arr[i];
        }else{
            current_maxValue=arr[i];
        }
        maxValue=max(current_maxValue,maxValue);
    }
    //求非环数组最小值
    int current_minValue=arr[0];
    int minValue=arr[0];
    for(int i=1;i<n;i++){
        if(current_minValue+arr[i]<arr[i]){
            current_minValue+=arr[i];
        }else{
            current_minValue=arr[i];
        }
        minValue=min(current_minValue,minValue);
    }
    //求数组和
    int totalSum=arr[0];
    for(int i=1;i<n;i++){
        totalSum+=arr[i];
    }
    int circle_Sum=0;
    if(totalSum==minValue){//如果数组和等于最小值和，意味着他们全部为负数，比如-3 -2 -1 -3 -5
        circle_Sum=maxValue;//最大值为-1
    }else{
        circle_Sum=max(totalSum-minValue,maxValue);
    }
    cout<<circle_Sum;
    return 0;
}
// 64 位输出请用 printf("%lld")