题目描述

给定一个长度为 $n$ 的整数序列，请选择一个连续且非空的子段，使这个子段中所有数字的乘积最大，并输出这个最大乘积。

输入格式

第一行输入一个整数 $n$。

第二行输入 $n$ 个整数，表示序列中的数字。

输出格式

输出一个整数，表示最大连续子段乘积。

输入输出样例

输入

4
2 3 -2 4

输出

6

数据范围与提示

对于全部数据，$1 \le n \le 1000$，序列中每个整数的绝对值不超过 $10$，保证答案在 64 位有符号整数范围内。

由于负数乘负数会变成正数，需要同时维护以当前位置结尾的最大乘积和最小乘积。

来源

GESP 6 级动态规划训练。