【解題】Maximum Product

ACM Volume CX 11059 - Maximum Product


The Problem

Given a sequence of integers S = {S₁, S₂, ..., S_n}, you should determine what is the value of the maximum positive product involving consecutive terms of S. If you cannot find a positive sequence, you should consider 0 as the value of the maximum product.


Input

Each test case starts with 1 ≤ N ≤ 18, the number of elements in a sequence. Each element S_i is an integer such that -10 ≤ S_i ≤ 10. Next line will have N integers, representing the value of each element in the sequence. There is a blank line after each test case. The input is terminated by end of file (EOF).


Output

For each test case you must print the message: Case #M: The maximum product is P., where M is the number of the test case, starting from 1, and P is the value of the maximum product. After each test case you must print a blank line.


Sample Input

3
2 4 -3

5
2 5 -1 2 -1


Sample Output

Case #1: The maximum product is 8.

Case #2: The maximum product is 20.


解題思考

　　對於這一題，直接利用暴力法就可以爆出來了。

　　換句話說，就是採用窮舉法，把所有連續數字的乘積都算出來，並從中找出最大值，就是答案了。


參考解答(C++)

#include <iostream>

using namespace std;

int main(void)
{
    int m = 1, n;
    while (cin >> n)
    {
        int *num = new int[n];
        for (int i = 0; i < n; i++)
        {
            cin >> num[i];
        }

        // 暴力法求解
        long long maximum = 0;
        for (int i = 0; i < n; i++)
        {
            long long product = 1;
            for (int j = i; j < n; j++)
            {
                product *= num[j];
                if (product > maximum)
                {
                    maximum = product;
                }
            }
        }

        cout << "Case #" << m++ << ": The maximum product is ";
        cout << maximum << "." << endl << endl;
    }

#ifndef ONLINE_JUDGE
    system("pause");
#endif
}