3006 - 最大子段积

给定一个整数数组ai,请你找出数组中乘积最大的连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。

输入

第一行为一个正整数n。 第二行为n个整数ai,之间用空格隔开。

输出

最大子段积。

样例

输入

6
2 3 -2 4 -1 -8

输出

48

提示

对于100%的数据,1≤n≤50, 1≤ai≤20。最大乘积会超过2^{63}-1

来源

动规专题

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题