同題: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