hdu 4561 小遊戲

小明和他的好朋友小西在玩一個遊戲，由電腦随機生成一個由-2，0，2三個數組成的數組，并且約定，誰先算出這個數組中某一段連續元素的積的最大值，就算誰赢！

比如我們有如下随機數組：

2 2 0 -2 0 2 2 -2 -2 0

在這個數組的衆多連續子序列中，2 2 -2 -2這個連續子序列的積為最大。

現在小明請你幫忙算出這個最大值。 

包含多組資料，每次輸入一個N值(1<=N=35)。

這道題我想了好半天，一直都是在想dp ,什麼狀态轉移方程，後來參考了一下别人的代碼，大部分的人都是以0為分界點，然後分别統計，但是找到了另外一種解法，發現思維很巧妙。。 詳細見代碼 #include <iostream>

using namespace std;

int main()

{

// freopen("I:\\in.txt","r",stdin);

int T,n,a[10010],i,j,k,sum,MAX,flag;

scanf("%d",&T);

k=1;

while(T--)

{

scanf("%d",&n);

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

{

scanf("%d",&a[i]);

}

MAX=0;

sum=0;

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

{

if (a[i]>0)

{

if (sum<0)

{

sum=sum-1;

}

else

sum=sum+1;

}

else if (a[i]<0)

{

if (sum<0)

{

sum=-sum+1;

}

else

sum=-sum-1;

}

else

sum=0;

if (sum>MAX)

{

MAX=sum;

}

}

        sum=0;

for (i=n-1;i>=0;i--)

{

if (a[i]>0)

{

if (sum<0)

{

sum=sum-1;

}

else

sum=sum+1;

}

else if (a[i]<0)

{

if (sum<0)

{

sum=-sum+1;

}

else

sum=-sum-1;

}

else

sum=0;

if (sum>MAX)

{

MAX=sum;

}

}

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

}

return 0;

}