以下是 LeetCode 3956. M 个非重叠子数组最大和 I 的 Python3 实现采用 前缀和 单调队列优化 DP时间复杂度从 O(n \cdot m \cdot (r-l1)) 优化到 O(n \cdot m)。解题思路状态定义dp[j][i] 表示前 i 个元素nums[0..i-1]恰好选 j 个子数组的最大和。状态转移dp[j][i] \max\left(dp[j][i-1],\;\; prefix[i] \max{t \in [i-r,\; i-l]} \big(dp[j-1][t] - prefix[t]\big)\right)- dp[j][i-1]不选以 i-1 结尾的子数组- 第二项选一个以 i-1 结尾、长度为 k ∈ [l,r] 的子数组令 t i-k单调队列优化对于固定的 j当 i 增加时窗口 [i-r,\; i-l] 向右滑动。用单调递减队列维护 dp[j-1][t] - prefix[t] 的最大值将内层循环优化到 O(1) 均摊。pythonfrom collections import dequeclass Solution:def maximumSum(self, nums: list[int], m: int, l: int, r: int) - int:n len(nums)# 前缀和prefix[i] nums[0] ... nums[i-1]prefix [0] * (n 1)for i in range(n):prefix[i 1] prefix[i] nums[i]NEG_INF float(-inf)# dp[j][i]前 i 个元素恰好选 j 个子数组的最大和dp [[NEG_INF] * (n 1) for _ in range(m 1)]# 选 0 个子数组和恒为 0辅助状态for i in range(n 1):dp[0][i] 0for j in range(1, m 1):# 单调递减队列存储 (t, dp[j-1][t] - prefix[t])q deque()for i in range(1, n 1):# 新进入窗口的 t i - lt_enter i - lif t_enter 0 and dp[j - 1][t_enter] ! NEG_INF:val dp[j - 1][t_enter] - prefix[t_enter]# 维护单调递减while q and q[-1][1] val:q.pop()q.append((t_enter, val))# 离开窗口的 t i - r - 1t_leave i - r - 1if q and q[0][0] t_leave:q.popleft()# 情况1不选以 i-1 结尾的子数组dp[j][i] dp[j][i - 1]# 情况2选一个以 i-1 结尾的子数组if q:dp[j][i] max(dp[j][i], prefix[i] q[0][1])# 至少选 1 个、至多 m 个子数组ans NEG_INFfor j in range(1, m 1):ans max(ans, dp[j][n])return ans关键点说明要点 说明dp[0][i] 0 前 i 个元素选 0 个子数组和为 0。这是从无到有选第一个子数组的基础窗口 [i-r,\; i-l] 子数组长度 k ∈ [l,r]对应起始位置 t i-k ∈ [i-r, i-l]单调队列 维护 dp[j-1][t] - prefix[t] 的递减序列队首即为当前窗口最大值t_enter / t_leave i 增加时窗口右移新进入 ti-l新离开 ti-r-1复杂度分析- 时间复杂度O(n \cdot m)每个 j 遍历一次 i单调队列均摊 O(1)- 空间复杂度O(n \cdot m)可滚动优化至 O(n)示例验证输入: nums [4,1,-5,2], m 2, l 1, r 3j1: dp[1] [0, 4, 5, 5, 5]最优子数组[4]→4, [4,1]→5, [4,1]→5, [4,1]→5j2: i4 时窗口 t∈[1,3]dp[1][3]-prefix[3]5-05dp[2][4] prefix[4] 5 2 5 7子数组 [4,1] 和 [2]和为 7输出: 7