ZeroJudge B917: Maximum Product

同題:UVa 11059 – Maximum Product

給定一系列整數 S = {S1、S2、…、SN},請找出最大的連續乘積。如果找不到正的連續乘積,則將 0 視為最大乘積。

範例測資

範例輸入範例輸出
EOF 輸入,每筆測資第一行有一個正整數 N,第二行有 N 個整數,代表要做乘法的數字。輸出測資編號和最大乘積,每筆資料中間需空一行
3
2 4 -3
5
2 5 -1 2 -1
Case #1: The maximum product is 8.
Case #2: The maximum product is 20.

解題思路

跑一個 For迴圈,這是每一次乘積的起點,在這個迴圈中再跑一個 For迴圈,從起點到 N-1。將一個變數 product 預設為 1,每一次 For迴圈都將目前跑到的數字乘到 product 中,並且每一次乘法都判斷最大值。本題需使用 Long Long Int。

範例程式碼-ZeroJudge B917: Maximum Product

#include <iostream>
#include <vector>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N, count = 1;
    while (cin >> N) {
        vector<int>num;
        long long int max = -999;
        for (int i = 0; i<N; i++) {
            int tmp;
            cin >> tmp;
            num.push_back(tmp);
        }
        for (int i = 0; i<N; i++) {
            long long int product = 1;
            for (int j = i; j<N; j++) {
                product *= num[j];
                if (product > max) max = product;
            }
        }
        cout << "Case #" << count << ": The maximum product is ";
        if (max < 0) cout << 0;
        else cout << max;
        cout << ".\n\n";
        count++;
    }
}

//ZeroJudge B917
//Dr. SeanXD

發佈留言