題意:


連續(xù)最大積
Time Limit: 3000/1000 MS (Java/Others) ? ?Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 1354 ? ?Accepted Submission(s): 458




Problem Description
小明和他的好朋友小西在玩一個游戲，由電腦隨機生成一個由-2，0，2三個數(shù)組成的數(shù)組，并且約定，誰先算出這個數(shù)組中某一段連續(xù)元素的積的最大值，就算誰贏！


比如我們有如下隨機數(shù)組：
2 2 0 -2 0 2 2 -2 -2 0?
在這個數(shù)組的眾多連續(xù)子序列中，2 2 -2 -2這個連續(xù)子序列的積為最大。


現(xiàn)在小明請你幫忙算出這個最大值。?
?


Input
第一行輸入一個正整數(shù)T，表示總共有T組數(shù)據(jù)(T <= 200)。
接下來的T組數(shù)據(jù)，每組數(shù)據(jù)第一行輸入N，表示數(shù)組的元素總個數(shù)（1<= N <= 10000）。
再接下來輸入N個由0，-2，2組成的元素，元素之間用空格分開。
?


Output
對于每組數(shù)據(jù)，先輸出Case數(shù)。
如果最終的答案小于等于0，直接輸出0
否則若答案是2^x ，輸出x即可。
每組數(shù)據(jù)占一行，具體輸出格式參見樣例。
?


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

思路:
? ? ?和最大連續(xù)子序列差不多,當0的時候置為0,要注意的事還有開個東西,記錄當前有多少個負數(shù),更新的時候只有偶數(shù)的時候在更新,就這樣,果斷敲完,果斷wa了,哎! 其實沒考慮到這個問題,-2 2 2 2 2 2 ?我們在倒著跑一便就能排除這種情況了,因為畢竟只有奇偶兩種情況...還有一點就是,如果最小的是-2那么只喲一種情況 就是只喲一個數(shù)字 并且這個數(shù)字是-2,自己稍微想下就明白,不解釋...

#include<stdio.h>#define N (10000 + 500) int num[N];int main () {int t ,n ,i ,ans_max ,cas = 1;scanf("%d" ,&t);while(t--){scanf("%d" ,&n);int mk0 = 0;for(i = 1 ;i <= n ;i ++){scanf("%d" ,&num[i]);if(num[i]) mk0 = 1;}printf("Case #%d: " ,cas ++);if(!mk0 || n == 1 && num[1] == -2) {printf("0\n");continue;}ans_max = 0;int now = 0;int ss = 0;for(i = 1 ;i <= n ;i ++){if(!num[i]){ss = now = 0;continue;}if(num[i] < 0) ss ++;now ++;if(ss % 2 == 0 && ans_max < now)ans_max = now;}now = 0;ss = 0;for(i = n ;i >= 1;i --){if(!num[i]){ss = now = 0;continue;}if(num[i] < 0) ss ++;now ++;if(ss % 2 == 0 && ans_max < now)ans_max = now;}printf("%d\n" ,ans_max);}return 0; }

總結

以上是生活随笔為你收集整理的hdu4561 连续最大积的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。