程序師世界是廣大編程愛好者互助、分享、學習的平台，程序師世界有你更精彩！
設為首頁 加入收藏
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> CSU 1529 Equator DP

CSU 1529 Equator DP

編輯：C++入門知識

CSU 1529 Equator DP


 

隊列優化DP

 

Equator Time Limit: 5000MS   Memory Limit: 131072KB   64bit IO Format: %lld & %llu

 

Submit Status

Description

\

 

Input

\

 

Output

\

 

Sample Input



3 3 1 2 3 8 4 5 -1 -1 1 -1 -1 5 2 -1 -1


Sample Output




6 14 0


 




 


 


/* ***********************************************
Author        :CKboss
Created Time  :2015年03月17日 星期二 20時13分17秒
File Name     :CSU1529.cpp
************************************************ */

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include

using namespace std;

const int maxn=2000200;

int n,ans;
int a[maxn];
int sum[maxn];
int dq[maxn],head,tail;

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

	int T_T;
	scanf("%d",&T_T);
	while(T_T--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",a+i); a[n+i]=a[i];
		}
		for(int i=1;i<=2*n;i++)
			sum[i]=sum[i-1]+a[i];
		
		head=0;tail=-1;ans=0;

		for(int i=1;i<=2*n;i++)
		{
			while((head<=tail)&&(sum[i]-sum[dq[tail]]<0))
			{
				ans=max(ans,sum[dq[tail]]-sum[dq[head]]);
				tail--;
			}
			while((head<=tail)&&(i-dq[head]>n))
			{
				ans=max(ans,sum[dq[tail]]-sum[dq[head]]);
				head++;
			}
			dq[++tail]=i;
		}

		printf("%d\n",ans);
	}
    
    return 0;
}






 


 


 

						


							

						

						
   

						
	
						

						
						
    
							
  1. 上一頁:
  2. 下一頁:
    3. 
						

					

				

				

					

						C++入門知識
						

					

					

						
						

							
							I/O多路復用服務器編程
							

		一、實驗目的
理解I/O多路復用技術的原理。
學會編寫
			
						

						
						

							
							你好，C++（40）7.1  一切指針都是紙老虎：徹底理解指針，7.1紙老虎
							
你好，C++（40）7.1  一切指針都是紙老虎：徹底理解指
			
						

						
						

							
							uva - 1368 - DNA Consensus String（字符串）
							

		題意：給你幾個字符串，找到一個字符串，使其到所有字符串
			
						

						
						

							
							設計模式C++描述----21.解釋器(Iterpreter)模式
							

		一. 解釋器模式

定義：給定一個語言，定義它的文法的
			
						

						
						

							
							基礎備忘：派生類直接訪問基類的私有成員
							

		派生類不能直接訪問基類的私有成員，若要訪問必須使用基類
			
						

						
						

							
							Hadoop Configuration配置類的分析
							
Hadoop Configuration配置類的分析
		 
			
						

						
						

					

				

			

			

				

					
相關文章

					
				
	
				
	
				

					

						
閱讀排行榜

					

					

						
						Good Article Good sentence Hdu
						
						hdu 2072 單詞數（STL  set寫法）
						
						[leetcode]Same Tree
						
						C++中的(unsigned int)&amp;amp;代表的意思
						
						我的STL學習之路，STL學習之路
						
						c++之靜態成員的初始化實例介紹
						
						從string類的實現看C++類的四大函數，string四大
						
						c++ auto_ptr智能指針，auto_ptr智能指針
						
						NOJ 1610
						
						C++ 判斷
						
						HDU 2569
						
					

				

				

					
熱門圖文

					

						
						
						
					

					

						
						js-Jquery 瀑布流應用，怎麼把它和數據庫對接
						
						用T4 Template生成代碼，t4template生成
						
						php文件類型對照手冊
						
						jsp操作Execl分析
						
						用戶界面設計風格說明(下)
						
						VC用Win API實現自繪按鈕類
						
						在.ashx文件中獲取cookies值實現代碼
						
						VC++下剖析黑客軟件隱蔽程序的手段
						
					

				

				

					
欄目導航

					

						C++基礎知識C++入門知識關於C++
					

					
				

			

			

		

	

		

	
Copyright © 程式師世界 All Rights Reserved