Description

张琪曼以数值的形式将人的一生的每个关键时间点以数值表示，快乐值越高，分值越高，痛苦值越高，分值越低甚至会成为负数。进一步研究，她又发现人性是复杂的，每个人的感知能力也是不尽相同的，例如有些人对其中某个时间段的感受其实是这段时间的各数值的乘积。比如说某个人的某个时间段中虽然仅有一个数值为负数即痛苦值，但因为各数值的乘积为负数，因此这段时间给他的感受是痛苦的。
现给n个整数序列（包含正数，0,负数），求最大连续子序列积。

Input Format

输入n(n≤10000)和n个整数。 n个整数的范围为-9~9

Output Format

输出该序列中最大和最小的连续子序列积，保证任何子序列的乘积都不超过long long类型取值范围。

5
-5 3 9 10 -5

6750
-1350

Source

动态规划