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

 

Sample Output

 

Source

2013金山西山居创意游戏程序挑战赛——复赛（2）

 

Recommend

liuyiding

 

把0看成隔板，把那一串数分成许多段，之后再计算每一小段里面最多有几个数的连续乘积是正数，再取一个最大值。

 

 

 

 

#include<stdio.h>

int a[50000+100],n;

int solve(int s,int e)

{

    int i,cnt=0,st,ed,flag=1,ans=0;

    if(s==n+1) return 0;

     for(i=s;i<e;i++)

     {

         if(a[i]==-2)

         {

             if(flag)  {flag=0;st=i;}

             ed=i;

             cnt++;

         }

     }

    if(cnt%2==0) return e-s;

    if(ans<st-s) ans=st-s;

    if(ans<e-st-1) ans=e-st-1;

    if(ans<e-ed-1) ans=e-ed-1;

    if(ans<ed-s)  ans=ed-s;

    return ans;

}

int main()

{

    int cas,i,k,ans;

    scanf("%d",&cas);

    for(k=1;k<=cas;k++)

    {

        ans=0;

        scanf("%d",&n);

        for(i=1;i<=n;i++)  scanf("%d",&a[i]);

        a[0]=0;

        for(i=0;i<=n;)

        {

            if(a[i]==0)

            {

               int ii=i+1;

                while(1)

                {

                    i++;

                    if(i==n+1||a[i]==0)

                        {

                             int mid=solve(ii,i);

                             if(ans<mid)  ans=mid;

                              break;

                        }

                }

            }

        }

        printf("Case #%d: %d\n",k,ans);

    }

   return 0;

}