连续最大积
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三个数组成的数组，并且约定，谁先算出这个数组中某一段连续元素的积的最大值，就算谁赢！
比如我们有如下随机数组：
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
思路:
和最大连续子序列差不多,当0的时候置为0,要注意的事还有开个东西,记录当前有多少个负数,更新的时候只有偶数的时候在更新,就这样,果断敲完,果断wa了,哎! 其实没考虑到这个问题,-2 2 2 2 2 2 我们在倒着跑一便就能排除这种情况了,因为毕竟只有奇偶两种情况...还有一点就是,如果最小的是-2那么只哟一种情况 就是只哟一个数字 并且这个数字是-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 "); 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 " ,ans_max); } return 0; }