算法-M个非重叠子数组最大和II-WQS二分学习
题目
给你一个长度为n的整数数组nums，以及三个整数m、l和r。
你的任务是从nums中选择至少一个且至多m个互不重叠的子数组，并满足：
- 每个被选择的子数组的长度都在
[l, r]范围内（包含两端）。 - 所有被选择子数组的总和最大。
返回你能够取得的最大总和。
子数组是数组中一个连续的非空元素序列。
示例 1：
输入：nums = [4,1,-5,2], m = 2, l = 1, r = 3
输出：7
解释：
一种最优策略是：
- 选择子数组
[4, 1]，其和为4 + 1 = 5；再选择子数组[2]，其和为 2。两个子数组的长度都在[l, r]范围内。 - 这些子数组的总和为
5 + 2 = 7，这是在至多m = 2个子数组下能够取得的最大总和。
题解
思路学习：WQS二分视频：WQS学习视频
class Solution { // DP 值, 子数组个数 private record Pair(long f, int cnt) { } // 相等的时候，子数组个数更大的劣 private boolean less(Pair a, Pair b) { return a.f < b.f || a.f == b.f && a.cnt > b.cnt; } public long maximumSum(int[] nums, int m, int l, int r) { int n = nums.length; long[] s = new long[n + 1]; // nums 的前缀和 long posSum = 0; // nums 中的正数之和 for (int i = 0; i < n; i++) { s[i + 1] = s[i] + nums[i]; if (nums[i] > 0) { posSum += nums[i]; } } Pair res0 = dpWithoutLimit(0, n, l, r, s); if (res0.cnt <= m) { // 直接满足题目要求 return res0.f; } // 现在专注于解决「选恰好 m 个子数组」的问题 long ans = 0; long left = 0; long right = posSum + 1; while (left + 1 < right) { long k = left + (right - left) / 2; Pair res = dpWithoutLimit(k, n, l, r, s); if (res.cnt <= m) { ans = res.f + m * k; // 见题解【细节 1】 right = k; } else { left = k; } } return ans; } // 没有 m 约束，但每选一个子数组就要把元素和减少 k private Pair dpWithoutLimit(long k, int n, int l, int r, long[] s) { Pair[] f = new Pair[n + 1]; Arrays.fill(f, 0, l, new Pair(0, 0)); Deque<Integer> q = new ArrayDeque<>(); Pair res = new Pair(Long.MIN_VALUE, 0); for (int i = l; i <= n; i++) { // 1. 入 int j = i - l; Pair v = new Pair(f[j].f - s[j], f[j].cnt); while (!q.isEmpty() && less(new Pair(f[q.peekLast()].f - s[q.peekLast()], f[q.peekLast()].cnt), v)) { q.pollLast(); } q.addLast(j); // 2. 更新答案 j = q.peekFirst(); Pair choose = new Pair(f[j].f - s[j] + s[i] - k, f[j].cnt + 1); if (less(res, choose)) { // choose 保证我们至少选了一个子数组 res = choose; } // 更新 DP f[i] = less(f[i - 1], choose) ? choose : f[i - 1]; // 3. 出，下一轮循环队首离开窗口 if (j <= i - r) { q.pollFirst(); } } return res; } }