记录编号	126146	评测结果	AAAAAAAAAA
题目名称	[福州培训2010] 最大和	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	0.077 s
提交时间	2014-10-11 09:27:04	内存使用	1.84 MiB

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <functional>
#define pritnf printf
#define scafn scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
using namespace std;
typedef long long LL;
typedef unsigned int Uint; 
const int INF=0x7ffffff;
const int MOD=1000000007;
//==============struct declaration==============

//==============var declaration=================
const int MAXN=100010;
long long S[MAXN*2];
int n;
LL ans=-0x7fffffff;
deque <int> Q;
//==============function declaration============

//==============main code=======================
int main()
{  
  freopen("maxsum.in","r",stdin);
  freopen("maxsum.out","w",stdout); 
  scanf("%d",&n);
  memset(S,0,sizeof(S));
  For(i,1,n) {
   scanf("%lld",S+i);
   S[i+n]=S[i];
  }
  For(i,1,n*2)
    S[i]+=S[i-1];
  Q.push_back(1);
  For(i,1,n*2){
    while (Q.front()<=i-n)
      Q.pop_front();
    ans=max(ans,S[i]-S[Q.front()-1]);
    while (!Q.empty()&&S[i-1]<S[Q.back()-1])
      Q.pop_back();
    Q.push_back(i);
  }
  pritnf("%d\n",ans);
  return 0;
}
//================fuction code====================