LeetCode 题解工作台
K 个不相交子数组的最大能量值
给你一个长度为 n 下标从 0 开始的整数数组 nums 和一个 正奇数 整数 k 。 x 个子数组的能量值定义为 strength = sum[1] * x - sum[2] * (x - 1) + sum[3] * (x - 2) - sum[4] * (x - 3) + ... + sum[x…
3
题型
5
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
对于第 个数 $nums[i - 1]$，如果它被选择，且位于第 个子数组，那么它对答案的贡献是 $nums[i - 1] \times (k - j + 1) \times (-1)^{j+1}$，我们不妨将 记为 ，那么它对答案的贡献是 $sign \times nums[i - 1] \times (k - j + 1)$。 我们定义 表示从前 $i 个数中选择 个子数组，且第 …
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个长度为 n 下标从 0 开始的整数数组 nums 和一个 正奇数 整数 k 。
x 个子数组的能量值定义为 strength = sum[1] * x - sum[2] * (x - 1) + sum[3] * (x - 2) - sum[4] * (x - 3) + ... + sum[x] * 1 ，其中 sum[i] 是第 i 个子数组的和。更正式的，能量值是满足 1 <= i <= x 的所有 i 对应的 (-1)i+1 * sum[i] * (x - i + 1) 之和。
你需要在 nums 中选择 k 个 不相交子数组 ，使得 能量值最大 。
请你返回可以得到的 最大能量值 。
注意，选出来的所有子数组 不 需要覆盖整个数组。
示例 1：
输入：nums = [1,2,3,-1,2], k = 3 输出：22 解释：选择 3 个子数组的最好方式是选择：nums[0..2] ，nums[3..3] 和 nums[4..4] 。能量值为 (1 + 2 + 3) * 3 - (-1) * 2 + 2 * 1 = 22 。
示例 2：
输入：nums = [12,-2,-2,-2,-2], k = 5 输出：64 解释：唯一一种选 5 个不相交子数组的方案是：nums[0..0] ，nums[1..1] ，nums[2..2] ，nums[3..3] 和 nums[4..4] 。能量值为 12 * 5 - (-2) * 4 + (-2) * 3 - (-2) * 2 + (-2) * 1 = 64 。
示例 3：
输入：nums = [-1,-2,-3], k = 1 输出：-1 解释：选择 1 个子数组的最优方案是：nums[0..0] 。能量值为 -1 。
提示：
1 <= n <= 104-109 <= nums[i] <= 1091 <= k <= n1 <= n * k <= 106k是奇数。
解题思路
方法一：动态规划
对于第 个数 ，如果它被选择，且位于第 个子数组，那么它对答案的贡献是 ，我们不妨将 记为 ，那么它对答案的贡献是 。
我们定义 表示从前 jif[i][j][1]ijif[0][0][1] = 0-\infty$。
当 时，我们考虑 如何进行状态转移。
如果第 个数不被选，那么第 个数既可以被选，也可以不被选，所以 。
如果第 个数被选，此时如果第 个数与第 个数位于同一个子数组中，那么 ，否则 。我们取这两种情况的最大值作为 。
最终答案是 。
时间复杂度 ，空间复杂度 。其中 是数组 的长度。
class Solution:
def maximumStrength(self, nums: List[int], k: int) -> int:
n = len(nums)
f = [[[-inf, -inf] for _ in range(k + 1)] for _ in range(n + 1)]
f[0][0][0] = 0
for i, x in enumerate(nums, 1):
for j in range(k + 1):
sign = 1 if j & 1 else -1
f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1])
f[i][j][1] = max(f[i][j][1], f[i - 1][j][1] + sign * x * (k - j + 1))
if j:
f[i][j][1] = max(
f[i][j][1], max(f[i - 1][j - 1]) + sign * x * (k - j + 1)
)
return max(f[n][k])
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
They want you to notice that Kadane-style greedy fails because each segment has a different signed weight slot.
- question_mark
They expect a DP state that separates closed states from currently extending a chosen subarray.
- question_mark
They are testing whether you can encode the exact strength formula directly into transitions instead of handling sums afterward.
常见陷阱
外企场景- error
Using a standard maximum k disjoint subarrays DP and forgetting that this problem's coefficients alternate sign and magnitude.
- error
Allowing overlap by starting a new subarray before the previous active subarray has been closed.
- error
Initializing impossible states incorrectly, which lets the DP fake fewer than k picks or open a segment at the wrong stage.
进阶变体
外企场景- arrow_right_alt
Change k from odd-only to any positive integer and keep the same DP shape with adjusted coefficient logic.
- arrow_right_alt
Ask for the minimum strength instead of maximum, which flips the optimization direction but keeps the transition structure.
- arrow_right_alt
Require returning the actual k subarray boundaries, which adds parent tracking on top of the same DP states.