LeetCode 3743. 循环划分的最大得分 — Python3 实现核心思路这道题的关键在于将子数组范围问题转化为股票交易问题- 子数组的范围 max - min- 按顺序遍历一个子数组时相当于一次交易在最小值处买入在最大值处卖出- 因此问题等价于在循环数组中最多进行 k 次交易每次收益为价格差的绝对值求最大总收益循环数组的处理循环数组需要在某处断开成线性数组。最优策略是在全局最小值处断开因为最小值天然适合作为子数组的边界它只可能是某个子数组的起点或终点不会夹在中间浪费得分。分别尝试从最小值位置和最小值后一个位置开始线性化取最大值。代码实现pythonclass 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 0for _ 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) % nx 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_dpresult max(result, dp[-1])return result# 在全局最小值处断开循环数组min_idx min(range(n), keylambda i: nums[i])return max(solve(min_idx), solve(min_idx 1))复杂度分析项目 复杂度时间 O(n × k)空间 O(n)可优化至 O(k)验证结果输入 输出 说明nums[1,2,3,3], k2 3 [2,3] 范围1, [3,1] 范围2nums[1,2,3,3], k1 2 整个数组范围3-12nums[1,2,3,3], k4 3 可少于k个子数组nums[1,5,1,5], k2 8 [1,5]×2各得4分下载完整代码[leetcode_3743.py](sandbox:///mnt/agents/output/leetcode_3743.py)
LeetCode 3743. 循环划分的最大得分 — Python3 实现核心思路这道题的关键在于将子数组范围问题转化为股票交易问题- 子数组的范围 max - min- 按顺序遍历一个子数组时相当于一次交易在最小值处买入在最大值处卖出- 因此问题等价于在循环数组中最多进行 k 次交易每次收益为价格差的绝对值求最大总收益循环数组的处理循环数组需要在某处断开成线性数组。最优策略是在全局最小值处断开因为最小值天然适合作为子数组的边界它只可能是某个子数组的起点或终点不会夹在中间浪费得分。分别尝试从最小值位置和最小值后一个位置开始线性化取最大值。代码实现pythonclass 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 0for _ 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) % nx 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_dpresult max(result, dp[-1])return result# 在全局最小值处断开循环数组min_idx min(range(n), keylambda i: nums[i])return max(solve(min_idx), solve(min_idx 1))复杂度分析项目 复杂度时间 O(n × k)空间 O(n)可优化至 O(k)验证结果输入 输出 说明nums[1,2,3,3], k2 3 [2,3] 范围1, [3,1] 范围2nums[1,2,3,3], k1 2 整个数组范围3-12nums[1,2,3,3], k4 3 可少于k个子数组nums[1,5,1,5], k2 8 [1,5]×2各得4分下载完整代码[leetcode_3743.py](sandbox:///mnt/agents/output/leetcode_3743.py)
