连续最大积

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 
    
     #include 
     
      using namespace std;int main(void){	int T;	int i;	cin>>T;	vector 
      
        vr;	for(i=0;i
       
        >N;		int j;				vector 
        
          vk;		for(j=0;j
         
          >k; vk.push_back(k); } int max=0; int temp=0; int cur=0; for(j=0;j
          
           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