51nod 1050 循环数组最大子段和

51nod 1050 循环数组最大子段和

虽然是板子题，两种做法，我们先写一种，另一个咕咕。

因为是循环，所以分为两种，中间的和两边的，中间的直接dp求最大，两边的转化一下就是总的数字和减去中间的最小数字和。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll a[500005];
int n;
int main() {
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
    }
    ll ans=0;
    ll mx=INT_MIN,cmx=0;
    ll mi=INT_MAX,cmi=0;
    for (int i=1;i<=n;i++) {
        cmx=max(a[i],cmx+a[i]);
        mx=max(mx,cmx);
        cmi=min(a[i],cmi+a[i]);
        mi=min(mi,cmi);
        ans+=a[i];
    }
    if(mx<0){
        cout<<0;
    }
    else{
    	cout<<max(mx,ans-mi);
	}
    return 0;
}