UVa 11059

題目

http://domen111.github.io/UVa-Easy-Viewer/?11059

給一個序列，問最大連續元素的乘積

想法

因為這題的 $N$ 很小，所以可以直接暴力做

枚舉開頭跟結尾，將其中的元素乘起來，並找出最大值

注意乘積可以到 $10^{18}$ ，記得開 long long

Code

#include<iostream>
using namespace std;
int n,arr[20],Case=1;
long long ans,tmp;
int main(){
	while(cin>>n){
		for(int i=0 ; i<n ; i++){
			cin>>arr[i];
		}
		ans=0;
		for(int i=0 ; i<n ; i++){
			// i 表示開頭
			tmp=1;
			for(int j=i ; j<n ; j++){
				// j 表示結尾
				tmp*=arr[j];
				ans=max(ans,tmp);
			}
		}
		cout<<"Case #"<<Case++<<": The maximum product is "<<ans<<".\n\n"; 
	}
	return 0;
}

時間複雜度分析

每筆測資輸入時間複雜度為 $O(n)$

枚舉答案的時間複雜度為 $O(n^2)$

每筆測資總時間複雜度為 $O(n+n^2)$ 約為 $O(n^2)$