HDOJ4561 連續最大積

連續最大積
Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 813    Accepted Submission(s): 305

Problem Description
小明和他的好朋友小西在玩一個游戲，由電腦隨機生成一個由-2，0，2三個數組成的數組，並且約定，誰先算出這個數組中某一段連續元素的積的最大值，就算誰贏！

比如我們有如下隨機數組：
2 2 0 -2 0 2 2 -2 -2 0
在這個數組的眾多連續子序列中，2 2 -2 -2這個連續子序列的積為最大。

現在小明請你幫忙算出這個最大值。
 

Input
第一行輸入一個正整數T，表示總共有T組數據(T <= 200)。
接下來的T組數據，每組數據第一行輸入N，表示數組的元素總個數（1<= N <= 10000）。
再接下來輸入N個由0，-2，2組成的元素，元素之間用空格分開。
 

Output
對於每組數據，先輸出Case數。
如果最終的答案小於等於0，直接輸出0
否則若答案是2^x ，輸出x即可。
每組數據占一行，具體輸出格式參見樣例。
 

Sample Input
2
2
-2 0
10
2 2 0 -2 0 2 2 -2 -2 0

Sample Output
Case #1: 0
Case #2: 4

#include <iostream>
#include <vector>
using namespace std;

int main(void)
{
	int T;
	int i;
	cin>>T;
	vector <int> vr;
	for(i=0;i<T;i++)
	{
		int N;
		cin>>N;
		int j;
		
		vector <int> vk;
		for(j=0;j<N;j++)
		{
			int k;
			cin>>k;
			vk.push_back(k);
		}

		int max=0;
		int temp=0;
		int cur=0;
		for(j=0;j<N;j++)
		{
			int k=vk[j];
			if(k>0)
				temp++;
			if(k<0)
			{
				if(cur!=0)
				{
					temp+=cur+1;
					cur=0;
				}
				else
				{
					if(temp>max)
						max=temp;
					cur=temp+1;
					temp=0;
				}
			}
			if(k==0||j==N-1)
			{
				if(temp>max)
					max=temp;
				temp=0;
				cur=0;
			}
		}
		temp=0;
		cur=0;
		for(j=N-1;j>-1;j--)
		{
			int k=vk[j];
			if(k>0)
				temp++;
			if(k<0)
			{
				if(cur!=0)
				{
					temp+=cur+1;
					cur=0;
				}
				else
				{
					if(temp>max)
						max=temp;
					cur=temp+1;
					temp=0;
				}
			}
			if(k==0||j==0)
			{
				if(temp>max)
					max=temp;
				temp=0;
				cur=0;
			}
		}
		vr.push_back(max);
	}





	for(i=0;i<T;i++)
	{
		cout<<"Case #"<<i+1<<": "<<vr[i]<<endl;
	}
	return 0;
}