这道题是 LeetCode 2945要求将一个数组分割成若干连续非空子数组使得每个子数组的和构成的序列是非递减的并且子数组的数量要最大不是子数组长度最大是段数最多。我重新写一个更清晰、直接能跑的 Java 实现并附上详细注释。javaclass Solution {public int findMaximumLength(int[] nums) {int n nums.length;// 1. 计算前缀和long[] pre new long[n 1];for (int i 0; i n; i) {pre[i 1] pre[i] nums[i];}// dp[i]前 i 个元素能分成的最大段数int[] dp new int[n 1];// last[i]前 i 个元素在最优分段下最后一段的和long[] last new long[n 1];// 单调队列存下标维护 pre[j] last[j] 单调递增int[] queue new int[n 1];int head 0, tail 0; // tail 指向下一个空位// 初始状态0 个元素0 段最后一段和为 0queue[tail] 0;for (int i 1; i n; i) {// 2. 从队头找到第一个满足 pre[j] last[j] pre[i] 的位置// 由于队列单调递增队头如果不满足后面都不满足但这里实际上要找满足条件的最右边// 正确做法弹出队头直到队头不满足然后前一个就是最优while (head 1 tail) {int j1 queue[head]; // 当前队头int j2 queue[head 1]; // 下一个元素if (pre[j2] last[j2] pre[i]) {head;} else {break;}}// 最优转移点 jint j queue[head];dp[i] dp[j] 1;last[i] pre[i] - pre[j];// 3. 将 i 加入队列维护队列单调性pre[k] last[k] 递增long val pre[i] last[i];while (head tail) {int k queue[tail - 1];if (pre[k] last[k] val) {tail--;} else {break;}}queue[tail] i;}return dp[n];}}核心思路说明1. 状态定义· dp[i]前 i 个元素能分成的最大段数· last[i]达到 dp[i] 时最后一段的和取最小的可能便于后续扩展2. 转移方程对于 i我们需要找一个 j i使得· 新的一段 [j1, i] 的和 sum pre[i] - pre[j]· 这个和必须 last[j]保证非递减· 转移dp[i] dp[j] 1last[i] sum为了段数最多j 要尽量大但不能太靠近 i否则 sum 会小。实际上可以证明在满足 sum last[j] 的前提下j 越大越好并且此时 last[i] 会尽可能小。3. 条件化简条件 pre[i] - pre[j] last[j]等价于 pre[i] pre[j] last[j]令 f(j) pre[j] last[j]对于固定的 i我们需要找到最大的 j 满足 f(j) pre[i]。4. 单调队列优化· 维护一个队列里面元素按 f(j) 单调递增· 同时因为要找最大的 j队头是满足条件的最优选择· 当 i 增加时pre[i] 增大队头可能不再是最优需要移动 head· 新加入 i 时f(i) pre[i] last[i] 可能会比某些尾部元素小需要弹出尾部维持单调性复杂度· 时间O(n)· 空间O(n)
DeepSeek LeetCode 2945. 找到最大非递减数组的长度 Java实现
发布时间：2026/6/3 9:47:27
这道题是 LeetCode 2945要求将一个数组分割成若干连续非空子数组使得每个子数组的和构成的序列是非递减的并且子数组的数量要最大不是子数组长度最大是段数最多。我重新写一个更清晰、直接能跑的 Java 实现并附上详细注释。javaclass Solution {public int findMaximumLength(int[] nums) {int n nums.length;// 1. 计算前缀和long[] pre new long[n 1];for (int i 0; i n; i) {pre[i 1] pre[i] nums[i];}// dp[i]前 i 个元素能分成的最大段数int[] dp new int[n 1];// last[i]前 i 个元素在最优分段下最后一段的和long[] last new long[n 1];// 单调队列存下标维护 pre[j] last[j] 单调递增int[] queue new int[n 1];int head 0, tail 0; // tail 指向下一个空位// 初始状态0 个元素0 段最后一段和为 0queue[tail] 0;for (int i 1; i n; i) {// 2. 从队头找到第一个满足 pre[j] last[j] pre[i] 的位置// 由于队列单调递增队头如果不满足后面都不满足但这里实际上要找满足条件的最右边// 正确做法弹出队头直到队头不满足然后前一个就是最优while (head 1 tail) {int j1 queue[head]; // 当前队头int j2 queue[head 1]; // 下一个元素if (pre[j2] last[j2] pre[i]) {head;} else {break;}}// 最优转移点 jint j queue[head];dp[i] dp[j] 1;last[i] pre[i] - pre[j];// 3. 将 i 加入队列维护队列单调性pre[k] last[k] 递增long val pre[i] last[i];while (head tail) {int k queue[tail - 1];if (pre[k] last[k] val) {tail--;} else {break;}}queue[tail] i;}return dp[n];}}核心思路说明1. 状态定义· dp[i]前 i 个元素能分成的最大段数· last[i]达到 dp[i] 时最后一段的和取最小的可能便于后续扩展2. 转移方程对于 i我们需要找一个 j i使得· 新的一段 [j1, i] 的和 sum pre[i] - pre[j]· 这个和必须 last[j]保证非递减· 转移dp[i] dp[j] 1last[i] sum为了段数最多j 要尽量大但不能太靠近 i否则 sum 会小。实际上可以证明在满足 sum last[j] 的前提下j 越大越好并且此时 last[i] 会尽可能小。3. 条件化简条件 pre[i] - pre[j] last[j]等价于 pre[i] pre[j] last[j]令 f(j) pre[j] last[j]对于固定的 i我们需要找到最大的 j 满足 f(j) pre[i]。4. 单调队列优化· 维护一个队列里面元素按 f(j) 单调递增· 同时因为要找最大的 j队头是满足条件的最优选择· 当 i 增加时pre[i] 增大队头可能不再是最优需要移动 head· 新加入 i 时f(i) pre[i] last[i] 可能会比某些尾部元素小需要弹出尾部维持单调性复杂度· 时间O(n)· 空间O(n)
