差分数组求区间多次累加后的最大值（Java实现）

这个问题可以用**差分数组 + 前缀和**来高效解决。因为 `n <= 99` 和 `q` 不限，但使用差分数组既能处理任意规模的 `q`，又能保持 O(n + q) 的时间复杂度。 ## 🧹 解题思路 差分数组 `diff` 的特点是： 对区间 `[L, R]` 增加 `x`，只需要： - `diff[L] += x` - `diff[R+1] -= x` 最后通过前缀和还原每个区域的干净度，然后取最大值即可。 ## 📐 算法步骤 1. 初始化大小为 `n+2` 的差分数组 `diff`（防止 R+1 越界）。 2. 对于每次打扫 `[L, R]` 加 `x`： - `diff[L] += x` - `diff[R+1] -= x` 3. 计算前缀和，得到每个区域的实际干净度。 4. 遍历所有区域，找出最大值并输出。 ## 💻 Java 代码实现 ```java public class CleanestArea { public static void main(String[] args) { int n = 99; // 区域总数 int q = 5; // 打扫次数（示例） // 模拟输入数据：每次打扫 [L, R] 和 xi int[][] cleans = { {1, 10, 3}, {5, 20, 2}, {15, 30, 4}, {25, 50, 1}, {45, 60, 5} }; // 差分数组，长度 n+2 防止越界 int[] diff = new int[n + 2]; // 应用差分 for (int[] clean : cleans) { int L = clean[0]; int R = clean[1]; int x = clean[2]; diff[L] += x; diff[R + 1] -= x; } // 前缀和还原并找最大值 int maxClean = 0; int current = 0; for (int i = 1; i <= n; i++) { current += diff[i]; if (current > maxClean) { maxClean = current; } } System.out.println("最干净区域的干净度是：" + maxClean); } } ``` ## ✅ 复杂度分析 - 时间复杂度：O(n + q) - 空间复杂度：O(n) ######[AI问答 | 569点数解答 | 2026-06-20 22:37:46]