题目描述

有一堆石头，用整数数组 $stones$ 表示。其中 $stones[i]$ 表示第 $i$ 块石头的重量。

每一回合，从中选出 任意两块石头 ，然后将它们一起粉碎。假设石头的重量分别为 $x$ 和 $y$，且 $x <= y$。那么粉碎的可能结果如下：

• 如果 $x == y$，那么两块石头都会被完全粉碎；
• 如果 $x != y$，那么重量为 $x$ 的石头将会完全粉碎，而重量为 $y$ 的石头新重量为 $y-x$。

最后， 最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 $0$。

输入格式

第一行一个整数 $n$ 表示石头的数量；

接下一行 $n$ 个空格隔开的整数表示各个石头的重量。

输出格式

一行一个整数表示答案。

示例 1：

6
2 7 4 1 8 1

1

解释:

组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，

组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，

组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，

组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

示例 2：

5
31 26 33 21 40

5

提示：

• $1 <= n <= 30$
• $1 <= stones[i] <= 100$

SOURCE

最后一块石头的重量 II