困难
给你一个整数数组 nums。
每次操作,你可以从当前数组中任选一个长度 至少为 2 的 子数组,并将其删除。该操作的代价为所选子数组的 首尾 元素之和。
每次操作后,将剩余元素按原有顺序拼接起来。
返回删除 整个 数组所需的 最小 总代价。
子数组 是数组中一段连续且 非空 的元素序列。
示例 1:
输入: nums = [2,-7,3,-5]
输出: -7
解释:
- 删除
[-7, 3],代价为-7 + 3 = -4。数组变为[2, -5]。 - 删除
[2, -5],代价为2 + (-5) = -3。 - 总代价为
-4 + (-3) = -7。
示例 2:
输入: nums = [4,0,-5,2]
输出: 1
解释:
- 删除
[0, -5],代价为0 + (-5) = -5。数组变为[4, 2]。 - 删除
[4, 2],代价为4 + 2 = 6。 - 总代价为
-5 + 6 = 1。
示例 3:
输入: nums = [7,-8,1]
输出: 8
解释:
- 要删除整个数组,必须在一次操作中删除全部三个元素。如果只删除两个元素,剩下的一个元素将无法删除。
- 删除
[7, -8, 1]的代价为7 + 1 = 8。
提示:
2 <= nums.length <= 105-109 <= nums[i] <= 109