class Solution {
public:
long long maxBalancedSubsequenceSum(vector<int>& nums) {
}
};
2926. 平衡子序列的最大和
给你一个下标从 0 开始的整数数组 nums 。
nums 一个长度为 k 的 子序列 指的是选出 k 个 下标 i0 < i1 < ... < ik-1 ，如果这个子序列满足以下条件，我们说它是 平衡的 ：
[1, k - 1] 内的所有 j ，nums[ij] - nums[ij-1] >= ij - ij-1 都成立。nums 长度为 1 的 子序列 是平衡的。
请你返回一个整数，表示 nums 平衡 子序列里面的 最大元素和 。
一个数组的 子序列 指的是从原数组中删除一些元素（也可能一个元素也不删除）后，剩余元素保持相对顺序得到的 非空 新数组。
示例 1：
输入：nums = [3,3,5,6] 输出：14 解释：这个例子中，选择子序列 [3,5,6] ，下标为 0 ，2 和 3 的元素被选中。 nums[2] - nums[0] >= 2 - 0 。 nums[3] - nums[2] >= 3 - 2 。 所以，这是一个平衡子序列，且它的和是所有平衡子序列里最大的。 包含下标 1 ，2 和 3 的子序列也是一个平衡的子序列。 最大平衡子序列和为 14 。
示例 2：
输入：nums = [5,-1,-3,8] 输出：13 解释：这个例子中，选择子序列 [5,8] ，下标为 0 和 3 的元素被选中。 nums[3] - nums[0] >= 3 - 0 。 所以，这是一个平衡子序列，且它的和是所有平衡子序列里最大的。 最大平衡子序列和为 13 。
示例 3：
输入：nums = [-2,-1] 输出：-1 解释：这个例子中，选择子序列 [-1] 。 这是一个平衡子序列，而且它的和是 nums 所有平衡子序列里最大的。
提示：
1 <= nums.length <= 105-109 <= nums[i] <= 109原站题解
golang 解法, 执行用时: 144 ms, 内存消耗: 9.4 MB, 提交时间: 2023-11-06 22:48:08
// 树状数组模板（维护前缀最大值）
type fenwick []int
func (f fenwick) update(i, val int) {
for ; i < len(f); i += i & -i {
f[i] = max(f[i], val)
}
}
func (f fenwick) preMax(i int) int {
mx := math.MinInt
for ; i > 0; i &= i - 1 {
mx = max(mx, f[i])
}
return mx
}
func maxBalancedSubsequenceSum(nums []int) int64 {
// 离散化 nums[i]-i
b := slices.Clone(nums)
for i := range b {
b[i] -= i
}
slices.Sort(b)
b = slices.Compact(b) // 去重
// 初始化树状数组
t := make(fenwick, len(b)+1)
for i := range t {
t[i] = math.MinInt
}
for i, x := range nums {
j := sort.SearchInts(b, x-i) + 1 // nums[i]-i 离散化后的值（从 1 开始）
f := max(t.preMax(j), 0) + x
t.update(j, f)
}
return int64(t.preMax(len(b)))
}
cpp 解法, 执行用时: 248 ms, 内存消耗: 60 MB, 提交时间: 2023-11-06 22:47:45
// 树状数组模板（维护前缀最大值）
class BIT {
vector<long long> tree;
public:
BIT(int n) : tree(n, LLONG_MIN) {}
void update(int i, long long val) {
while (i < tree.size()) {
tree[i] = max(tree[i], val);
i += i & -i;
}
}
long long pre_max(int i) {
long long res = LLONG_MIN;
while (i > 0) {
res = max(res, tree[i]);
i &= i - 1;
}
return res;
}
};
class Solution {
public:
long long maxBalancedSubsequenceSum(vector<int> &nums) {
int n = nums.size();
// 离散化 nums[i]-i
auto b = nums;
for (int i = 0; i < n; i++) {
b[i] -= i;
}
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end()); // 去重
BIT t = BIT(b.size() + 1);
for (int i = 0; i < n; i++) {
// j 为 nums[i]-i 离散化后的值（从 1 开始）
int j = lower_bound(b.begin(), b.end(), nums[i] - i) - b.begin() + 1;
long long f = max(t.pre_max(j), 0LL) + nums[i];
t.update(j, f);
}
return t.pre_max(b.size());
}
};
java 解法, 执行用时: 64 ms, 内存消耗: 58.3 MB, 提交时间: 2023-11-06 22:47:26
class Solution {
public long maxBalancedSubsequenceSum(int[] nums) {
int n = nums.length;
int[] b = new int[n];
for (int i = 0; i < n; i++) {
b[i] = nums[i] - i;
}
Arrays.sort(b);
BIT t = new BIT(b.length + 1);
for (int i = 0; i < n; i++) {
// j 为 nums[i]-i 离散化后的值（从 1 开始）
int j = Arrays.binarySearch(b, nums[i] - i) + 1;
long f = Math.max(t.preMax(j), 0) + nums[i];
t.update(j, f);
}
return t.preMax(b.length);
}
}
// 树状数组模板（维护前缀最大值）
class BIT {
private long[] tree;
public BIT(int n) {
tree = new long[n];
Arrays.fill(tree, Long.MIN_VALUE);
}
public void update(int i, long val) {
while (i < tree.length) {
tree[i] = Math.max(tree[i], val);
i += i & -i;
}
}
public long preMax(int i) {
long res = Long.MIN_VALUE;
while (i > 0) {
res = Math.max(res, tree[i]);
i &= i - 1;
}
return res;
}
}
python3 解法, 执行用时: 1504 ms, 内存消耗: 39 MB, 提交时间: 2023-11-06 22:47:10
class Solution:
def maxBalancedSubsequenceSum(self, nums: List[int]) -> int:
b = sorted(set(x - i for i, x in enumerate(nums))) # 离散化 nums[i]-i
t = BIT(len(b) + 1)
for i, x in enumerate(nums):
j = bisect_left(b, x - i) + 1 # nums[i]-i 离散化后的值（从 1 开始）
f = max(t.pre_max(j), 0) + x
t.update(j, f)
return t.pre_max(len(b)) # 所有 f 的最大值
# 树状数组模板（维护前缀最大值）
class BIT:
def __init__(self, n: int):
self.tree = [-inf] * n
def update(self, i: int, val: int) -> None:
while i < len(self.tree):
self.tree[i] = max(self.tree[i], val)
i += i & -i
def pre_max(self, i: int) -> int:
mx = -inf
while i > 0:
mx = max(mx, self.tree[i])
i &= i - 1
return mx