Kimi LeetCode 3956. M 个非重叠子数组最大和 I Java实现

以下是 LeetCode 3956. M 个非重叠子数组最大和 I 的完整 Java 实现javaimport java.util.ArrayDeque;class Solution {public long maximumSum(int[] nums, int m, int l, int r) {int n nums.length;long[] prefix new long[n 1];for (int i 0; i n; i) {prefix[i 1] prefix[i] nums[i];}long NEG_INF Long.MIN_VALUE / 4;// dp[i][k]考虑前 i 个元素恰好选 k 个子数组的最大总和long[][] dp new long[n 1][m 1];// 初始化选 0 个子数组时和为 0其余状态为负无穷for (int i 0; i n; i) {for (int k 1; k m; k) {dp[i][k] NEG_INF;}}for (int k 1; k m; k) {ArrayDequeInteger dq new ArrayDeque(); // 单调递减队列存下标for (int i 1; i n; i) {// 1) 不选以 i-1 结尾的子数组dp[i][k] dp[i - 1][k];// 2) 将新的候选下标 j i - l 加入队列int j i - l;if (j 0) {long val dp[j][k - 1] - prefix[j];while (!dq.isEmpty()) {int last dq.peekLast();long lastVal dp[last][k - 1] - prefix[last];if (lastVal val) {dq.pollLast();} else {break;}}dq.addLast(j);}// 3) 移除滑出窗口的候选下标 i - rwhile (!dq.isEmpty() dq.peekFirst() i - r) {dq.pollFirst();}// 4) 用队首最优候选更新 dpif (!dq.isEmpty()) {int best dq.peekFirst();long candidate prefix[i] dp[best][k - 1] - prefix[best];dp[i][k] Math.max(dp[i][k], candidate);}}}// 答案在 1~m 个子数组中取最大题目要求至少选一个long ans NEG_INF;for (int k 1; k m; k) {ans Math.max(ans, dp[n][k]);}return ans;}}---核心思路步骤 说明前缀和 prefix[i] 表示 nums[0..i-1] 的和用于 O(1) 计算任意子数组和DP 定义 dp[i][k] 前 i 个元素中恰好选 k 个合法子数组的最大总和转移方程 不选结尾元素dp[i][k] dp[i-1][k]选一个以 i-1 结尾、长度在 [l,r] 的子数组dp[i][k] max(dp[i-len][k-1] sum[i-len..i-1])单调队列优化 将转移改写为 prefix[i] max(dp[j][k-1] - prefix[j])其中 j ∈ [i-r, i-l]。用单调队列维护窗口最大值将复杂度从 O(n·m·r) 降到 O(n·m)复杂度- 时间复杂度O(n · m)n, m ≤ 1000约 10⁶ 次操作- 空间复杂度O(n · m)DP 数组约 8 MB