1050?循環數組最大子段和
N個整數組成的循環序列a[1],a[2],a[3],…,a[n]，求該序列如a[i]+a[i+1]+…+a[j]的連續的子段和的最大值（循環序列是指n個數圍成一個圈，因此需要考慮a[n-1],a[n],a[1],a[2]這樣的序列）。當所給的整數均為負數時和為0。
例如：-2,11,-4,13,-5,-2，和最大的子段為：11,-4,13。和為20。
?
Input
第1行：整數序列的長度N（2?<=?N?<=?50000)
第2?-?N+1行：N個整數?(-10^9?<=?S[i]?<=?10^9) Output
輸出循環數組的最大子段和。 Input示例
6
-2
11
-4
13
-5
-2 Output示例
20
—————————————————————————————
這道題有兩種情況
第一種就是正常的選連續一段
第二種是在尾開始頭結束
這種情況下肯定是因為中間有一段是負的而且這個負的最小
所以只要求一下最小的連續一段用總的值去減掉就好了
#include<cstdio> #include<cstring> #include<algorithm> #define LL long long using namespace std; const int M=1e5+7; int read(){int ans=0,f=1,c=getchar();while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}return ans*f; } int n,m,s[M]; LL sum,ans,mn,tot; int main(){n=read();for(int i=1;i<=n;i++) s[i]=read(),tot+=s[i];for(int i=1;i<=n;i++){sum+=s[i];if(sum<0) sum=0;else ans=max(ans,sum);}sum=0;for(int i=1;i<=n;i++){sum+=s[i];if(sum>0) sum=0;else mn=min(mn,sum);}ans=max(ans,tot-mn);printf("%lld\n",ans);return 0; }
? 
