算法-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)); DequeInteger 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; } }