连续最大积

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