Kimi LeetCode 3743. 循环划分的最大得分 Python3实现

LeetCode 3743. 循环划分的最大得分 — Python3 实现

核心思路

这道题的关键在于将子数组范围问题转化为股票交易问题：

- 子数组的范围 = `max - min`
- 按顺序遍历一个子数组时，相当于一次"交易"：在最小值处"买入"，在最大值处"卖出"
- 因此问题等价于：在循环数组中最多进行 k 次交易，每次收益为价格差的绝对值，求最大总收益

循环数组的处理

循环数组需要在某处"断开"成线性数组。最优策略是：在全局最小值处断开，因为最小值天然适合作为子数组的边界（它只可能是某个子数组的起点或终点，不会夹在中间浪费得分）。

分别尝试从最小值位置和最小值后一个位置开始线性化，取最大值。

代码实现

```python
class Solution:
def maximumScore(self, nums: list[int], k: int) -> int:
n = len(nums)

def solve(base: int) -> int:
"""
将循环数组从 base 位置开始线性化，DP求解最多k次交易的最大收益。
"""
dp = [0] * (n + 1) # dp[j]: 前j个元素的最大得分
result = 0

for _ in range(k):
# x = max(dp[j] - nums[idx]): 最优"最小值起点"
# y = max(dp[j] + nums[idx]): 最优"最大值起点"
x, y = float("-inf"), float("-inf")
new_dp = [float("-inf")] * (n + 1)

for j in range(n):
idx = (base + j) % n

x = max(x, dp[j] - nums[idx])
y = max(y, dp[j] + nums[idx])

# 三种选择：
# 1. 不在j结束子数组 → new_dp[j]
# 2. 以nums[idx]为最大值结束 → x + nums[idx]
# 3. 以nums[idx]为最小值结束 → y - nums[idx]
new_dp[j + 1] = max(new_dp[j], x + nums[idx], y - nums[idx])

dp = new_dp
result = max(result, dp[-1])

return result

# 在全局最小值处断开循环数组
min_idx = min(range(n), key=lambda i: nums[i])
return max(solve(min_idx), solve(min_idx + 1))
```

复杂度分析

项目 复杂度
时间 O(n × k)
空间 O(n)（可优化至 O(k)）

验证结果

输入 输出 说明
`nums=[1,2,3,3], k=2` 3 `[2,3]` 范围=1, `[3,1]` 范围=2
`nums=[1,2,3,3], k=1` 2 整个数组范围=3-1=2
`nums=[1,2,3,3], k=4` 3 可少于k个子数组
`nums=[1,5,1,5], k=2` 8 `[1,5]`×2，各得4分

下载完整代码：[leetcode_3743.py](sandbox:///mnt/agents/output/leetcode_3743.py)