5200. Bare Minimum Difference

单点时限: 1.0 sec

内存限制: 1024 MB

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

  1. 每一个数必须属于一个区间。
  2. 区间的数量必须不少于两个。

例如 $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, \ldots, a_n$ ($1 \leq a_i \leq 10^6$),中间以空格分隔,分别表示数组的每个元素。

输出格式

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

样例

Input
6
3 1 4 5 3 1
Output
1
Input
8
3 7 6 9 1 2 4 9
Output
4

提示

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

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

135 人解决,198 人已尝试。

157 份提交通过,共有 584 份提交。

3.6 EMB 奖励。

创建: 7 月,2 周前.

修改: 7 月,2 周前.

最后提交: 2 周,6 天前.

来源: N/A

题目标签
DP