Problem #5200 - ECNU Online Judge

单点时限: 1.0 sec

内存限制: 1024 MB

对于一个长度为 $n$ 的数组，其合法划分需要将数组划分成若干个区间并满足以下条件：

例如 $n = 5$ 时， $[1, 2], [3, 3], [4, 5]$ ， $[1, 3], [4, 5]$ 就是合法的划分，而 $[1, 2], [4, 5]$ ， $[1, 5]$ 就是不合法的划分。

Antiamuny 定义一个区间的价值为区间内所有元素之和，一个划分的优秀值为划分内的最大区间价值和最小区间价值之差。

现在，Antiamuny 想知道，对于给定的数组可以得到的最小的优秀值是多少，请你写个程序帮帮他。

第一行包含一个整数 $n$ ( $2 \leq n \leq 100$ )，表示数组的长度。

第二行包含 $n$ 个整数 $a_{1}, a_{2}, \dots, a_{n}$ ( $1 \leq a_{i} \leq 10^{6}$ )，中间以空格分隔，分别表示数组的每个元素。

在一行输出一个整数，表示可以得到的最小的优秀值。

Input

6
3 1 4 5 3 1

Output

Input

8
3 7 6 9 1 2 4 9

Output

样例一： $[1, 3], [4, 6]$ 是一个可行的划分,各个区间的价值分别为 $8, 9$ 。

样例二： $[1, 2], [3, 3], [4, 4], [5, 7], [8, 8]$ 是一个可行的划分，各个区间的价值分别为 $10, 6, 9, 7, 9$ 。

143 人解决，208 人已尝试。

166 份提交通过，共有 625 份提交。

3.6 EMB 奖励。

创建: 1 年，7 月前.

修改: 1 年，7 月前.

最后提交: 1 月前.

来源: N/A

DP

5200. Bare Minimum Difference