题意
给一串整数 S，你需要找到其连续子序列中乘积最大的那个，输出其乘积。如果找到的答案不是正数，那么输出 0，表示无解。
另外注意：每组输入后面都有一行空格，每组输出后面也应该有一个空行。输入以 EOF 结束。
输入 #1复制
3 2 4 -3 5 2 5 -1 2 -1
输出
Case #1: The maximum product is 8. Case #2: The maximum product is 20.
思路:暴力枚举.
- 另外也可以只确定子序列左边的下标,右边的进行待定,直接走一遍,边走边进行更新.
- 先确定子序列左边的下标,再确定右边的下标,然后分别求解,更新结果.
需要注意,由于输入的是多行,每个样例之间有一个空行,这里应该放在样例的输出后面进行处理.
参考代码1
#include<iostream> #include<algorithm> using namespace std; int arr[20],case1,n; long long temp,ans; int main() { while(cin>>n){ // if(case1){ // cout<<endl; // } for(int i = 0;i < n;i++){ cin>>arr[i]; } ans = 0; for(int i = 0;i < n;i++){//子序列左边的下标 temp = 1; for(int j = i;j<n;j++){// 子序列右边的下标待定,边后移边进行判断更新. temp *= arr[j]; ans = max(ans,temp); } } cout<<"Case #"<<++case1<<": The maximum product is "<<ans<<"."<<endl<<endl; } }
参考代码2
#include<iostream> #include<algorithm> using namespace std; int arr[20],n,case1; long long temp,ans;//防止越界. int main() { while(cin>>n){ for(int i = 0;i < n;i++){ cin>>arr[i]; } ans = 0; for(int i = 0; i<n;i++) //子序列的左下标 for(int j = i; j < n;j++){//子序列的右下标 右下标不能从i+1开始,因为可能所有的数中只有一个整数,那么这个整数就是子序列.子序列可以只有一个数字 temp = 1; for(int k = i; k <= j; k++){ temp *= arr[k]; //ans = max(temp,ans);这个应该放在外边,对这个子序列求完之后再更新ans. } ans = max(temp,ans); } cout<<"Case #"<<++case1<<": The maximum product is "<<ans<<"."<<endl<<endl; } return 0; }
