A signal passes through a chain of n amplifiers; amplifier i multiplies it by a[i], which may be negative or zero. Choose a non-empty run of consecutive amplifiers that gives the largest product, and print that product.
Constraints
- 1 ≤ n ≤ 14
- −6 ≤ a[i] ≤ 6
Input and output
- Input
- The first line has n. The second line has n integers.
- Output
- One integer: the largest product of a non-empty contiguous run.
Examples
Input 1
4
2 -3 -2 4Output
48The whole array: 2 × −3 × −2 × 4 = 48.
Input 2
3
-4 0 -2Output
0Any run containing both negatives also contains 0; the best is 0.
Show hints
- A negative number turns the smallest product into the largest.
- Track both the largest and the smallest product of a run ending at each position.
Show the explanation
Unlike sums, a very negative product becomes very positive after one more negative factor. So keep two values for the run ending at each index: the largest (hi) and the smallest (lo) product. For a new value x, the candidates are x, hi·x and lo·x; the new hi is the largest of the three and the new lo the smallest. A zero resets both naturally.
Original UniCircle question. Last reviewed 22 Oct 2026.