b917 - 11059 Maximum Product
題目描述
題目要求找出一個整數序列中，連續項的最大正積。如果找不到正數序列，則最大積為 0。
解題思路
此題採用暴力法解決。遍歷所有可能的連續子序列，計算每個子序列的乘積，並記錄最大的正乘積。由於序列長度不大（最大為 18），暴力法可以有效地找到答案。程式碼中，外層迴圈 i 決定子序列的起始位置，內層迴圈 j 決定子序列的結束位置。在內層迴圈中，計算從 a[i] 到 a[j] 的乘積，並與當前最大乘積 ans 進行比較，更新 ans。
複雜度分析
- 時間複雜度: O(n^2)
- 空間複雜度: O(n)
程式碼
#include <iostream>
using namespace std;
int main(){
int c=0,n;
while(cin >> n){
cout << "Case #" << ++c << ": The maximum product is ";
int a[n];
for(int i=0;i<n;++i)
cin >> a[i];
long long int ans=0;
for(int i=0;i<n;++i){
long long int temp=1;
for(int j=i;j<n;++j){
temp*=a[j];
if(temp>ans)ans=temp;
}
}
cout << ans << ".\n\n";
}
}