題目

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。

輸入

第1行：整數序列的長度N（2 <= N <= 50000)
第2 - N+1行：N個整數 (-10^9 <= S[i] <= 10^9)

輸出

輸出循環數組的最大子段和。

輸入樣例

6
-2
11
-4
13
-5
-2

輸出樣例

20

思路：求前綴和后使用雙端隊列模擬即可

源程序

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #define PI acos(-1.0) #define E 1e-12 #define INF 0x3f3f3f3f #define LL long long const int MOD=1000000007; const int N=100000+5; const int dx[]= {-1,1,0,0}; const int dy[]= {0,0,-1,1}; using namespace std;deque<int> Q; LL sum[N]; LL v[N]; int main() {int n;scanf("%d",&n);Q.clear();sum[0]=0;LL ans=-INF;Q.push_back(0);for(int i=1; i<=n; i++) {scanf("%lld",&v[i]);sum[i]=sum[i-1]+v[i];}for(int i=n+1; i<=2*n; i++) {sum[i]=sum[i-1]+v[i-n];}for(int i=1; i<=2*n; i++) {while(!Q.empty() && Q.front()<i-n)Q.pop_front();ans=max(ans,sum[i]-sum[Q.front()]);while(!Q.empty() && sum[Q.back()]>=sum[i])Q.pop_back();Q.push_back(i);}printf("%lld\n",ans);return 0; }

?

總結

以上是生活随笔為你收集整理的循环数组最大字段和（51Nod-1050）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。