跳转至

4123. 删除数组的最小代价

难度困难

题目描述

给你一个整数数组 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

解法

方法一

1

1

1

1

评论