企业官网建设流程全解析

这道题是 LeetCode 2945，要求将一个数组分割成若干连续非空子数组，使得每个子数组的和构成的序列是非递减的，并且子数组的数量要最大（不是子数组长度最大，是段数最多）。

我重新写一个更清晰、直接能跑的 Java 实现，并附上详细注释。

```java
class 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 段，最后一段和为 0
queue[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;
}
}

// 最优转移点 j
int 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，使得：

· 新的一段 [j+1, i] 的和 sum = pre[i] - pre[j]
· 这个和必须 >= last[j]（保证非递减）
· 转移：dp[i] = dp[j] + 1，last[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)