最大乘积（Maximum Product，UVa 11059）

题目链接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=84562#problem/B

题意：

输入n个元素组成的序列S，找出一个乘积最大的连续子序列。如果这个最大的乘积不是正数，输出0(表示无解)。1<=n<=18，-10<=Si<=10。每一个案例之间用空白行分隔，案例输出要求输出"Case #M: The maximum product is P.",其中M为案例号，P为乘积值。

案例：

Sample Input

2 4 -3

2 5 -1 2 -1

Sample Output

Case #1: The maximum product is 8.

Case #2: The maximum product is 20.

分析：

连续的子序列有两个要素，即起点和终点，因此只需枚举起点和终点即可，由于至多18个元素且绝对值不超过10，最大乘积不超过10的18次方，可以使用long long型存储。

源代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 const int maxn=20;
 5 int a[maxn];
 6 int main()
 7 {
 8     int N,i,j,t,ant=0;
 9     long long k,max;//注意输入18位数全为10时，k和max数据过大
10     while(scanf("%d",&N)!=EOF)//数据量
11     {   
12         ant++;
13         for(i=0;i<N;i++)//数据
14             cin>>a[i];
15         max=0;//最大乘积值
16         for(i=0;i<N;++i)//起始位置
17         {   
18             for(j=i;j<N;j++)//结束点位置
19             {   k=1;
20                 for(t=i;t<=j;t++)//起点至终点数据乘积
21                     k*=a[t];
22                 if(max<k)//最大乘积值判断
23                     max=k;
24             }
25         }
26         printf("Case #%d: The maximum product is %lld.
",ant,max);//输出语句控制
27         if(ant) cout<<endl;
28     }
29     return 0;
30 }