千问 LeetCode 2926. 平衡子序列的最大和 Java实现
这是一道经典的动态规划（DP）结合离散化与树状数组（或线段树）优化的题目。
💡 核心解题思路
1. 题目转化：
题目要求平衡子序列满足 nums[ij] - nums[ij-1] >= ij - ij-1。
我们将不等式移项变形，得到 nums[ij] - ij >= nums[ij-1] - (ij-1)。
如果我们定义一个新数组 b[i] = nums[i] - i，那么题目就转化为：在原数组中找一个下标递增的子序列，使得对应的 b[i] 也是非递减的，并且原数组 nums 的元素和最大。
2. 动态规划定义：
设 dp[i] 表示以 nums[i] 结尾的平衡子序列的最大和。
状态转移方程为：dp[i] = max(0, max{dp[j]}) + nums[i]，其中 j < i 且 b[j] <= b[i]。
（max(0, ...) 是因为如果前面的最大和是负数，我们不如直接从 nums[i] 重新开始）。
3. 数据结构优化：
如果直接暴力遍历 j，时间复杂度是 O(N^2)，会超时。我们需要一种数据结构来快速求出所有满足 b[j] <= b[i] 的 dp[j] 中的最大值。
这正好是树状数组（Binary Indexed Tree, BIT）或线段树的强项，它们可以在 O(logN) 的时间内完成“前缀最大值查询”和“单点更新”。
4. 离散化：
由于 nums[i] 的范围很大（-10^9 到 10^9），b[i] 的值域也非常大，不能直接作为树状数组的下标。因此，我们需要先对 b[i] 进行离散化（排序并去重，映射到 1 到 N 的排名）。
💻 Java 代码实现
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
public long maxBalancedSubsequenceSum(int[] nums) {
int n = nums.length;
// 1. 预处理 b[i] = nums[i] - i，并进行离散化
int[] b = new int[n];
for (int i = 0; i < n; i++) {
b[i] = nums[i] - i;
}
// 复制一份 b 数组用于排序去重
int[] sortedB = b.clone();
Arrays.sort(sortedB);
// 去重
int m = 1;
for (int i = 1; i < n; i++) {
if (sortedB[i] != sortedB[i - 1]) {
sortedB[m++] = sortedB[i];
}
}
// 2. 初始化树状数组（用于维护前缀最大值）
// 树状数组下标从 1 开始，所以大小为 m + 1
long[] bit = new long[m + 1];
// 初始化为极小值
Arrays.fill(bit, Long.MIN_VALUE);
long globalMax = Long.MIN_VALUE;
// 3. 遍历原数组，进行状态转移
for (int i = 0; i < n; i++) {
// 二分查找当前 b[i] 在离散化数组中的排名（从 1 开始）
int rank = Arrays.binarySearch(sortedB, 0, m, b[i]) + 1;
// 查询所有 b[j] <= b[i] 的最大 dp[j]（即树状数组的前缀最大值）
long prevMax = query(bit, rank);
// 状态转移：如果前面的最大和是负数，不如从当前 nums[i] 重新开始
long currentDp = Math.max(0L, prevMax) + nums[i];
// 更新全局最大值
globalMax = Math.max(globalMax, currentDp);
// 将当前 dp 值更新到树状数组中
update(bit, rank, currentDp);
}
return globalMax;
}
// 树状数组查询前缀最大值：查询 [1, idx] 范围内的最大值
private long query(long[] bit, int idx) {
long max = Long.MIN_VALUE;
while (idx > 0) {
max = Math.max(max, bit[idx]);
idx -= idx & -idx;
}
return max;
}
// 树状数组单点更新：将 idx 位置的值更新为 max(bit[idx], val)
private void update(long[] bit, int idx, long val) {
while (idx < bit.length) {
bit[idx] = Math.max(bit[idx], val);
idx += idx & -idx;
}
}
}
📊 复杂度分析
* 时间复杂度：O(N log N)。排序离散化需要 O(N log N)，遍历数组时，每次二分查找、树状数组的查询和更新都是 O(log N)，总时间复杂度为 O(N log N)。
* 空间复杂度：O(N)。需要额外的数组存储离散化后的 b 以及树状数组。
⚠️ 易错点提示
1. 数据溢出：题目中 nums[i] 的和可能会超过 int 的范围，因此 dp 状态、树状数组以及最终结果必须使用 long 类型。
2. 负数处理：树状数组初始值需要设为 Long.MIN_VALUE。在状态转移时，一定要和 0 取最大值（Math.max(0L, prevMax)），因为如果前面的最优解是负数，我们完全可以舍弃前面的部分，只保留当前的 nums[i]。
3. 离散化去重：在排序后一定要进行去重操作，否则树状数组的大小会超出预期，且二分查找的排名会出错。