首页 > 代码库 > HLG 2116 Maximum continuous product (最大连续积 DP)

HLG 2116 Maximum continuous product (最大连续积 DP)

链接:  http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=2116

Description

Wind and his GF(game friend) are playing a small game. They use the computer to randomly generated a number sequence which only include number 2,0 and -2. To be the winner,wind must 

have to find a continuous subsequence whose continuous product is maximum.

For example, we have a sequence blow:

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

Among all of it‘s continuous subsequences, 2 2 -2 -2 own the maximum continuous product.

(2*2*(-2)*(-2) = 16 ,and 16 is the maximum continuous product)

You,wind‘s friend,can give him a hand.

Input

The first line is an integer T which is the Case number(T <= 200).

For each test case, there is an integer N indicating the length of the number sequence.(1<= N <= 10000)

The next line,there are N integers which only include 2,0 and -2.

Output

For each case,you have to output the case number first(Reference the sample).

If the answer is smaller than 0, you just need to output 0 as the answer.

If the answer‘s format is 2^x,you need to output the x as the answer.

Output the answer in one line.

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


代码如下:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstring>
#define MAXN 15000
#define RST(N)memset(N, 0, sizeof(N))
using namespace std;

int n, ans, cas, T = 1;
int a[MAXN], mn[MAXN], mx[MAXN];

void Init()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    RST(mx), RST(mn), ans = 0;
}

int solve()
{
    for(int i=1; i<=n; i++) {
        if(a[i] > 0) {
            if(mn[i-1] > 0) mn[i] = mn[i-1]+1;
            mx[i] = mx[i-1]+1;
        }else if(a[i] < 0) {
            if(mn[i-1] > 0) mx[i] = mn[i-1]+1;
            if(mx[i-1] > 0) mn[i] = mx[i-1]+1;
            else mn[i] = 1;
        }else {
            mx[i] = 0;
            mn[i] = 0;
        }
        ans = max(ans, mx[i]);
    }
    return ans;
}

int main()
{
    scanf("%d", &cas);
    while(cas--) {
        Init();
        printf("Case #%d: %d\n", T++, solve());
    }
    return 0;
}