HDOJ 4561連続最大積

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
小明と彼の良い友达の小西は1つのゲームを游んで、コンピュータからランダムに1つの-2,0,2の3つの数からなる配列を生成して、しかも约束して、谁が先にこの配列の中である1段の连続要素の积み重ねの最大値を算出して、たとえ谁が胜っても!
たとえば、次のランダム配列があります.
2 2 0 -2 0 2 2 -2 -2 0 
この配列の多くの連続サブシーケンスの中で,2 2−2−2という連続サブシーケンスの積が最大であった.
今、明ちゃんはこの最大値を算出してください.
 
 
Input
1行目には、T組のデータが合計であることを示す正の整数Tが入力される(T<=200).
次のT組のデータは、各組のデータの最初の行にNを入力し、配列の要素の総個数(1<=N<=10000)を表す.
次に0,−2,2からなるN個の要素を入力し,要素間をスペースで区切る.
 
 
Output
データのセットごとにCase数を出力します.
最終的な答えが0以下の場合は、0を直接出力します.
そうでなければ答えが2^xであればxを出力すればよい.
各グループのデータは1行を占め、具体的な出力フォーマットはサンプルを参照してください.
 
 
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;

}