地主拥有 nn 个技能，技能从 11 开始编号，依次为 11 到 nn，编号为 ii 的技能拥有 a_ia i ​ 的威力 ( a_ia i ​ 可能为负 )。地主不仅会使用某一个技能攻击对手，他还会使用组合技能，更具体地，他会将一段编号连续的技能组合起来攻击对手，而这个组合技能的威力就是这些编号连续的技能的威力的和的绝对值。 现在 \text{Smart}Smart 手上有一个特殊技能，可以将地主所有 nn 个技能的威力都减少同一个任意实数值 ( 可以为负 )。为了安全起见，小 G 希望能通过这个技能，使地主的组合技能威力最大值尽量小。

解题思路：

首先可以发现，如果我们将所有技能的威力都减去同一个实数值，那么组合技能的威力之和并不会改变，因为减法是可交换的。

因此，我们可以先将所有技能的威力都减去一个初始值，这样原问题就转化为了求减去初始值之后的技能威力之和的最小连续子段和（注意这里是最小，不是最大）。

我们可以用前缀和数组 sum_i 表示前 i 个技能威力之和，则减去初始值之后的技能威力之和为 sum_j - sum_i，其中 j > i。

那么问题就转化为了求 sum_j - sum_i 的最小值，即 sum_i - sum_j 的最大值。我们可以遍历所有的 i，记录前面出现过的最大的 sum_k，那么对于当前的 i，最大的 sum_k 就是 i 之前的前缀和的最小值，我们只需要用当前的 sum_i 减去最大的 sum_k，就是以 i 结尾的最小连续子段和。

最后我们在所有的以 i 结尾的最小连续子段和中取最小值，即为答案。

代码实现：

相关问题

地主拥有 nn 个技能，技能从 11 开始编号，依次为 11 到 nn，编号为 ii 的技能拥有 a_ia i ​ 的威力 ( a_ia i ​ 可能为负 )。地主不仅会使用某一个技能攻击对手，他还会使用组合技能，更具体地，他会将一段编号连续的技能组合起来攻击对手，而这个组合技能的威力就是这些编号连续的技能的威力的和的绝对值。 现在 \text{Smart}Smart 手上有一个特殊技能，可以将地主所有 nn 个技能的威力都减少同一个任意实数值 ( 可以为负 )。为了安全起见，小 G 希望能通

过使用特殊技能来尽可能地减小地主使用组合技能攻击对手的威力。请你帮助小 G 求出地主使用组合技能攻击对手的最小威力值。

输入格式
第一行包含一个整数 nn。

第二行包含 nn 个整数 a_1,a_2,…,a_na
1
​
,a
2
​
,…,a
n
​
。

输出格式
输出一个整数，表示地主使用组合技能攻击对手的最小威力值（即最小的威力值的绝对值）。

数据范围
1≤n≤1051≤n≤105
|a_i|≤109∣a
i
​
∣≤109

输入样例：
5
-1 2 -3 4 -5
输出样例：
1
输入样例2：
6
-2 -3 4 -5 -6 -7
输出样例2：
1

题目分析：

看到要求最小值，我们自然想到用二分去求解

代码：

Smart 正在玩一款名叫 “OI” 的益智类游戏，他遇到的首个任务是斗地主。 当然这个任务不是让你上手来一盘 ”斗地主”，而是要解决一个问题： 地主拥有 nn 个技能，技能从 11 开始编号，依次为 11 到 nn，编号为 ii 的技能拥有 a_ia i ​ 的威力 ( a_ia i ​ 可能为负 )。地主不仅会使用某一个技能攻击对手，他还会使用组合技能，更具体地，他会将一段编号连续的技能组合起来攻击对手，而这个组合技能的威力就是这些编号连续的技能的威力的和的绝对值。 现在 \text{Sm

art} 想知道地主能够使用的组合技能中，威力最小的那个组合技能的威力是多少？

解题思路：
- 这道题需要用到前缀和的思想，我们可以预处理出前缀和数组 sum，其中 sum_i 表示前 i 个技能威力之和。
- 对于任意两个技能 i 和 j，它们之间的技能威力和为 abs(sum_j - sum_i + a_i)，我们可以枚举所有可能的组合技能，求出它们的威力，并取最小值即可。

代码实现：