2926. 平衡子序列的最大和(2448)

给你一个下标从 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：

1
2
3
4
5
6
7
8
输入：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：

1
2
3
4
5
6
输入：nums = [5,-1,-3,8]
输出：13
解释：这个例子中，选择子序列 [5,8] ，下标为 0 和 3 的元素被选中。
nums[3] - nums[0] >= 3 - 0 。
所以，这是一个平衡子序列，且它的和是所有平衡子序列里最大的。
最大平衡子序列和为 13 。

示例 3：

1
2
3
4
输入：nums = [-2,-1]
输出：-1
解释：这个例子中，选择子序列 [-1] 。
这是一个平衡子序列，而且它的和是 nums 所有平衡子序列里最大的。

提示：

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9

树状数组维护前缀最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class FenwickTree {
    long[] tr;  // [1, n]
    public FenwickTree(int[] nums) {  // [0, n-1]
        this.tr = new long[nums.length+1];
        Arrays.fill(tr, Long.MIN_VALUE);
    }
    public int lowbit(int x) {
        return x & (-x);
    }
    public void add(int i, long val) {
        while (i < tr.length) {
            tr[i] = Math.max(tr[i], val);
            i += lowbit(i);
        }
    }
    public long query(int i) {
        long res = Long.MIN_VALUE;
        while (i > 0) {
            res = Math.max(res, tr[i]);
            i -= lowbit(i);
        }
        return res;
    }
}
class Solution {
    public long maxBalancedSubsequenceSum(int[] nums) {
        // nums[i] - nums[j] >= i - j
        // nums[i] - i >= nums[j] - j
        // 定义 b[i]=nums[i] − i，问题变成从 b 中选出一个非降子序列，求对应的 nums 的元素和的最大值
        int n = nums.length, b[] = new int[n];
        for (int i = 0; i < n; i++) {
            b[i] = nums[i] - i;
        }
        Arrays.sort(b);
        // （虽然这里用dp数组，但这里并没有动态规划。。当时理解错了吧）
        // 定义dp[i]表示子序列最后一个数的下标为i时，对应的nums的元素和的最大值
        // 考虑当前状态i时，我们需要找到所有满足j<i的dp[j]的最大值
        // 这里可以用树状数组（或线段树）来维护前缀最大值
        FenwickTree tree = new FenwickTree(nums);
        long dp[] = new long[n];
        for (int i = 0; i < n; i++) {
            int idx = Arrays.binarySearch(b, nums[i] - i) + 1;  // 离散化后的坐标（从1开始）
            dp[i] = Math.max(tree.query(idx), 0) + nums[i];
            tree.add(idx, dp[i]);
        }
        // return tree.query(n);  // 也可以
        return Arrays.stream(dp).max().getAsLong();
    }
}