以下是 LeetCode 3957. M 个非重叠子数组最大和 II 的完整 Java 实现。解题思路这道题的核心难点在于- 子数组长度可变在 [l, r] 范围内- 子数组个数上限为 m至多 m 个至少 1 个- 数组元素可为负数- 数据规模 n ≤ 10^5m ≤ n暴力 DPO(n·m)会超时解法WQS 二分Alien Trick 单调队列优化 DP1. WQS 二分Alien Trick对于至多选 m 个子数组的约束直接做分层 DP 是 O(n·m) 的。WQS 二分的核心思想是 给每个选中的子数组附加一个惩罚值 λ将原问题转化为无个数限制的问题最大化 sum - λ·cnt。定义 g(λ) max(sum - λ·cnt)设达到该最优解时使用了 c(λ) 个子数组。关键性质c(λ) 随 λ 增大而单调不增。对于凹函数 h(k)至多 k 个子数组的最大和有h(m) min_λ (g(λ) λ·m)通过二分搜索 λ找到使得 c(λ) ≤ m 的最小 λ即可得到答案 g(λ) λ·m。2. 单调队列优化对于固定的 λDP 转移方程为dp[i] max(dp[i-1], max_{s∈[i-r, i-l]} (dp[s] pref[i] - pref[s] - λ)) max(dp[i-1], pref[i] - λ max_{s∈[i-r, i-l]} (dp[s] - pref[s]))其中 max_{s∈[i-r, i-l]} (dp[s] - pref[s]) 可以用单调队列在 O(1) 均摊时间内维护整体复杂度 O(n)。3. 边界情况处理- 所有子数组和为非正数此时至多 m 个的最优策略是选 0 个和为 0但题目要求至少选 1 个所以答案应为最大单个子数组和可能为负数。- 无限制最优解已满足 cnt ≤ m直接返回无需二分。---Java 代码javaimport java.util.*;class Solution {public long maximumSum(int[] nums, int m, int l, int r) {int n nums.length;// 前缀和long[] pref new long[n 1];for (int i 0; i n; i) {pref[i 1] pref[i] nums[i];}// 步骤1计算单个子数组的最大和长度在[l,r]内long maxSingle computeMaxSingle(pref, l, r);// 若所有合法子数组和都≤0则必须恰好选1个最不差那个if (maxSingle 0) {return maxSingle;}// 步骤2检查无个数限制时λ0是否已满足 cnt ≤ mResult unconstrained solve(nums, pref, l, r, 0);if (unconstrained.cnt m) {return unconstrained.val; // 无需惩罚直接返回}// 步骤3WQS二分搜索惩罚值 λ// h(m) min_λ (g(λ) λ·m)long lo 1;long hi (long) 1e12;long ans Long.MAX_VALUE;while (lo hi) {long mid lo (hi - lo) / 2;Result res solve(nums, pref, l, r, mid);if (res.cnt m) {// 惩罚足够大子数组数已压到≤m// h(m) g(λ) λ·mlong candidate res.val mid * (long) m;ans Math.min(ans, candidate);hi mid - 1;} else {// 惩罚太小子数组仍太多lo mid 1;}}return ans;}// 计算长度在[l,r]范围内的单个子数组的最大和private long computeMaxSingle(long[] pref, int l, int r) {int n pref.length - 1;long maxSum Long.MIN_VALUE / 4;// 单调队列维护递增的 pref[s]队首即为最小值DequeInteger dq new ArrayDeque();for (int i l; i n; i) {int s i - l;while (!dq.isEmpty() pref[dq.peekLast()] pref[s]) {dq.pollLast();}dq.offerLast(s);// 移除超出长度限制r的起点while (!dq.isEmpty() dq.peekFirst() i - r) {dq.pollFirst();}if (!dq.isEmpty()) {maxSum Math.max(maxSum, pref[i] - pref[dq.peekFirst()]);}}return maxSum;}private static class Result {long val; // max(sum - λ·cnt)int cnt; // 使用的子数组个数最小化Result(long val, int cnt) {this.val val;this.cnt cnt;}}// 对给定惩罚λ求 max(sum - λ·cnt) 及对应最小cnt// 单调队列优化O(n)private Result solve(int[] nums, long[] pref, int l, int r, long lambda) {int n nums.length;long[] dpVal new long[n 1];int[] dpCnt new int[n 1];// 单调队列元素[dpVal[s] - pref[s], dpCnt[s], s]// 按值递减值相同时按cnt递增保留更小的cntDequelong[] dq new ArrayDeque();for (int i 1; i n; i) {// 入队s i - l 成为合法起点if (i - l 0) {long sVal dpVal[i - l] - pref[i - l];int sCnt dpCnt[i - l];while (!dq.isEmpty()) {long[] last dq.peekLast();if (last[0] sVal || (last[0] sVal last[1] sCnt)) {dq.pollLast();} else {break;}}dq.offerLast(new long[]{sVal, sCnt, i - l});}// 出队移除长度超过r的起点while (!dq.isEmpty() dq.peekFirst()[2] i - r) {dq.pollFirst();}// 选项1不选以i-1结尾的子数组long bestVal dpVal[i - 1];int bestCnt dpCnt[i - 1];// 选项2选一个以i-1结尾的子数组if (!dq.isEmpty()) {long[] front dq.peekFirst();long candVal front[0] pref[i] - lambda;int candCnt (int) front[1] 1;if (candVal bestVal || (candVal bestVal candCnt bestCnt)) {bestVal candVal;bestCnt candCnt;}}dpVal[i] bestVal;dpCnt[i] bestCnt;}return new Result(dpVal[n], dpCnt[n]);}}---复杂度分析项目 复杂度时间复杂度 O(n · log C)其中 C 是二分搜索范围约 10^12需 40 次迭代。每次迭代内 DP 为 O(n)单调队列均摊 O(1)。空间复杂度 O(n)前缀和数组与 DP 数组。验证示例输入 输出 说明nums[4,1,-5,2], m2, l1, r3 7 [4,1] [2] 52 7nums[1,0,3,4], m2, l1, r2 8 [1] [3,4] 17 8nums[-1,7,-4], m1, l2, r3 6 [-1,7] 6nums[-3,-4,-1], m2, l1, r2 -1 全负数选 [-1] -1