Setting

Bob needs money, and since he knows you are here, he decided to gamble intelligently. The game is rather simple: each player gets a sequence of integers. The players must determine, by using their mega-pocket computers, which is the maximum product value which can be computed with non empty sub-sequences of consecutive numbers from the given sequence. The winner is the one which gets first the right result.

Can you help Bob with a program to compute quickly the wanted product, particularly when the sequence is quite long?

Input

The input file contains sequences of numbers. Each number will have at most 5 digits. There will be at most 100 numbers in each sequence. Each sequence starts on a new line and may continue on several subsequent lines. Each sequence ends with the number -999999 (which is not part of the sequence).

Output

The maximum sub-sequence product for each sequence must be written on the standard output, on a different line. A simple example is illustrated in the sample below.

Sample Input

1 2 3 -999999
-5 -2 2 -30 -999999
-8 -999999
-1 0 -2 -999999

Sample Output

6
120
-8
0

This is challenge 787 of the ACM International Collegiate Programming Contest. Test input is provided by uDebug.

Upload Solution

Please log in to submit your solution.

Statistics

Difficulty (2 votes)
Average test runtime 0.59
Points (changes over time) 10
Tried by 4 users
Solved by 3 users

Global ranking

# Name Runtime Points worth
1 Sven 0.24 18
2 AlexanderP 0.58 7
3 Mac 0.95 5