hdu 4561 模擬小題

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

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

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;
}