紫书例题7-2 最大乘积

Posted on | In |

输入n个元素组成的序列s，你需要找出一个乘积最大的连续子序列。如果这个最大的成绩不是正数，应输入-1（表示无解）。输入0结束输入。1<=n<=18,-10<=Si<=10。
样例输入：

3

2 4 -3

样例输出：

8

20

思路

枚举起点与终点

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>
#include<vector>
using namespace std;
int main(){
	int n;
	int a[100];
	while(~scanf("%d",&n)){
		if(n==0) break;
		for(int i=0;i<n;i++)
		scanf("%d",&a[i]);
	int max=-1;
	//i,j控制循环次数 
	for(int i=0;i<n-1;i++){
	
		for(int j=i+1;j<n;j++){
				int sum=1; 
			for(int k=i;k<=j;k++) //!!!
					sum*=a[k];
			if(sum>max) max=sum;
				cout<<sum<<endl;
		}
	
	}
	cout<<max<<endl;
		}
	
	
	
	return 0;
}