Description

Given a sequence of integers S = {S1, S2, . . . , Sn}, you should determine what is the value of themaximum positive product involving consecutive terms of S. If you cannot find a positive sequence,you should consider 0 as the value of the maximum product.

Input

Each test case starts with 1 ≤ N ≤ 18, the number of elements in a sequence. Each element Si is an integer such that −10 ≤ Si ≤ 10. Next line will have N integers, representing the value of each element in the sequence. There is a blank line after each test case. The input is terminated by end of file (EOF).

Output

For each test case you must print the message: ‘Case #M: The maximum product is P.’, where M is the number of the test case, starting from 1, and P is the value of the maximum product. After each test case you must print a blank line.

Sample Input

3

2 4 -3

5

2 5 -1 2 -1

Sample Output

Case #1: The maximum product is 8.

Case #2: The maximum product is 20.

题意：

输入n个元素组成的序列S，你需要找出一个乘积最大的连续子序列。如果这个最大的乘积不是正数，应输出0（表示无解）。1 ≤ N ≤ 18，−10 ≤ Si ≤ 10。

 

分析：

1.连续子序列有两个要素：起点和终点，只要枚举起点和终点即可。

2.每个元素的绝对值不超过10且不超过18个元素，最大可能的乘积不会超过10^18。

3.最大可能超过 int 的范围，可用 long long 进行存储。

4.每个案例用空格隔开。

 

代码：

1 #include
     
       2 #include
      
        3 using namespace std; 4  5 int main() 6 { 7     int n,a[20]; 8     int i,j; 9     int M=0;10     while(scanf("%d",&n)!=EOF)11     {12         long long P=0;//最大乘积13         for(i=0;i
       
        P)22                     P=mid_ans;23             }24         }25         M++;26         if(P>0)27             printf("Case #%d: The maximum product is %lld.\n\n",M,P);28         else 29             printf("Case #%d: The maximum product is 0.\n\n",M);30     }31     return 0;32 }
       
      
     

 

心得：

long long 类型在VC里不能编译成功，在VC里应用_int64 类型。后来用code：：blocks编译通过了。观察几个提交的程序发现其实有些不必要的语句可以省略，这样可以使程序更简化，更清晰易懂。