千问 LeetCode 2926. 平衡子序列的最大和 C++实现

这道题的 C++ 解法思路与 Java 完全一致，核心都是通过离散化配合树状数组（BIT）来优化动态规划。

在 C++ 中，我们可以利用 std::vector 结合标准库自带的 sort、unique 和 lower_bound 来非常优雅地实现离散化。

💻 C++ 代码实现

#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

class Solution {
public:
long long maxBalancedSubsequenceSum(vector<int>& nums) {
int n = nums.size();

// 1. 预处理 b[i] = nums[i] - i，并进行离散化
vector<int> b(n);
for (int i = 0; i < n; i++) {
b[i] = nums[i] - i;
}

// 复制一份 b 数组用于排序去重
vector<int> sortedB = b;
sort(sortedB.begin(), sortedB.end());
// 去重
sortedB.erase(unique(sortedB.begin(), sortedB.end()), sortedB.end());

int m = sortedB.size();
// 2. 初始化树状数组（用于维护前缀最大值），下标从 1 开始
vector<long long> bit(m + 1, LLONG_MIN);

long long globalMax = LLONG_MIN;

// 3. 遍历原数组，进行状态转移
for (int i = 0; i < n; i++) {
// 二分查找当前 b[i] 在离散化数组中的排名（从 1 开始）
int rank = lower_bound(sortedB.begin(), sortedB.end(), b[i]) - sortedB.begin() + 1;

// 查询所有 b[j] <= b[i] 的最大 dp[j]（即树状数组的前缀最大值）
long long prevMax = query(bit, rank);

// 状态转移：如果前面的最大和是负数，不如从当前 nums[i] 重新开始
long long currentDp = max(0LL, prevMax) + nums[i];

// 更新全局最大值
globalMax = max(globalMax, currentDp);

// 将当前 dp 值更新到树状数组中
update(bit, rank, currentDp);
}

return globalMax;
}

private:
// 树状数组查询前缀最大值：查询 [1, idx] 范围内的最大值
long long query(vector<long long>& bit, int idx) {
long long maxVal = LLONG_MIN;
while (idx > 0) {
maxVal = max(maxVal, bit[idx]);
idx -= idx & -idx;
}
return maxVal;
}

// 树状数组单点更新：将 idx 位置的值更新为 max(bit[idx], val)
void update(vector<long long>& bit, int idx, long long val) {
while (idx < bit.size()) {
bit[idx] = max(bit[idx], val);
idx += idx & -idx;
}
}
};

📊 复杂度分析
* 时间复杂度：O(N log N)。排序离散化需要 O(N log N)，遍历数组时，每次二分查找、树状数组的查询和更新都是 O(log N)。
* 空间复杂度：O(N)。需要额外的 vector 存储离散化后的数组以及树状数组。

⚠️ C++ 实现注意事项
1. 数据溢出：与 Java 一样，累加和极易超出 int 范围，因此状态变量、树状数组以及返回值必须使用 long long。
2. 极小值初始化：C++ 中 long long 的极小值可以使用 <climits> 头文件中的 LLONG_MIN。
3. 离散化工具：
* sort 用于排序。
* unique 会将重复元素移到容器末尾，并返回去重后的逻辑末尾迭代器。
* 必须配合 erase 才能真正删除末尾的重复元素。
* lower_bound 是 C++ 标准库中的二分查找函数，返回第一个大于等于目标值的迭代器。
4. 类型转换：在 max(0LL, prevMax) 中，写成 0LL 是为了明确告诉编译器这是一个 long long 类型的 0，避免与 long long 比较时出现类型警告或错误。