What defines a balanced subsequence in Maximum Balanced Subsequence Sum?

A balanced subsequence requires nums[j] - nums[i] >= j - i for every consecutive pair of indices i and j.

Can a single element subsequence be considered balanced?

Yes, any subsequence of length 1 is automatically balanced according to the problem rules.

What is the best approach for large arrays?

Use dynamic programming with a segment tree or binary indexed tree to efficiently query maximum dp values.

How does state transition dynamic programming apply here?

State dp[x] tracks the max sum ending at index x, and each dp[x] is updated using valid predecessors y that meet the balance condition.

Are negative numbers handled in the maximum sum computation?

Yes, dp[x] considers negative nums[x] values, and the algorithm still finds the subsequence yielding the largest total sum.

#2926

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

平衡子序列的最大和

给你一个下标从 0 开始的整数数组 nums 。 nums 一个长度为 k 的子序列指的是选出 k 个下标 i 0 1 k-1 ，如果这个子序列满足以下条件，我们说它是平衡的：对于范围 [1, k - 1] 内的所有 j ， nums[i j ] - nums[i j-1 ] >= i …

数组二分查找动态规划树状数组线段树

题目描述

给你一个下标从 0 开始的整数数组 nums 。

nums 一个长度为 k 的 子序列 指的是选出 k 个下标 i₀ < i₁ < ... < i_k-1 ，如果这个子序列满足以下条件，我们说它是 平衡的 ：

对于范围 [1, k - 1] 内的所有 j ，nums[i_j] - nums[i_j-1] >= i_j - i_j-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 <= 10⁵
-10⁹ <= nums[i] <= 10⁹

lightbulb

解题思路

方法一：动态规划 + 树状数组

根据题目描述，我们可以将不等式 $nums[i] - nums[j] \ge i - j$ 转化为 $nums[i] - i \ge nums[j] - j$ ，因此，我们考虑定义一个新数组 $arr$ ，其中 $arr[i] = nums[i] - i$ ，那么平衡子序列满足对于任意 $j \lt i$ ，都有 $arr[j] \le arr[i]$ 。即题目转换为求在 $arr$ 中选出一个递增子序列，使得对应的 $nums$ 的和最大。

假设 $i$ 是子序列中最后一个元素的下标，那么我们考虑子序列倒数第二个元素的下标 $j$ ，如果 $arr[j] \le arr[i]$ ，我们可以考虑是否要将 $j$ 加入到子序列中。

因此，我们定义 $f[i]$ 表示子序列最后一个元素的下标为 $i$ 时，对应的 $nums$ 的最大和，那么答案为 $\max_{i=0}^{n-1} f[i]$ 。

状态转移方程为：

f[i] = \max(\max_{j=0}^{i-1} f[j], 0) + nums[i]

其中 $j$ 满足 $arr[j] \le arr[i]$ 。

我们可以使用树状数组来维护前缀的最大值，即对于每个 $arr[i]$ ，我们维护前缀 $arr[0..i]$ 中 $f[i]$ 的最大值。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $nums$ 的长度。

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

class BinaryIndexedTree:
    def __init__(self, n: int):
        self.n = n
        self.c = [-inf] * (n + 1)

    def update(self, x: int, v: int):
        while x <= self.n:
            self.c[x] = max(self.c[x], v)
            x += x & -x

    def query(self, x: int) -> int:
        mx = -inf
        while x:
            mx = max(mx, self.c[x])
            x -= x & -x
        return mx


class Solution:
    def maxBalancedSubsequenceSum(self, nums: List[int]) -> int:
        arr = [x - i for i, x in enumerate(nums)]
        s = sorted(set(arr))
        tree = BinaryIndexedTree(len(s))
        for i, x in enumerate(nums):
            j = bisect_left(s, x - i) + 1
            v = max(tree.query(j), 0) + x
            tree.update(j, v)
        return tree.query(len(s))

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check if your DP correctly handles subsequences of length 1 automatically.
question_mark
Verify whether your state transition correctly enforces nums[j] - nums[i] >= j - i.
question_mark
Consider edge cases with negative numbers or decreasing sequences that can affect the maximum sum.

warning

常见陷阱

外企场景

error
Forgetting the balance condition and summing arbitrary subsequences.
error
Assuming consecutive elements in the array can always be part of the subsequence.
error
Inefficient O(n^2) DP without segment tree or binary search optimization.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Maximum Balanced Subsequence Product where multiplication is used instead of sum.
arrow_right_alt
Longest Balanced Subsequence focusing on length rather than sum.
arrow_right_alt
Balanced Subsequence with additional constraints like fixed subsequence length k.

help

常见问题

外企场景

继续练习

#2916 子数组不同元素数目的平方和 II #2940 找到 Alice 和 Bob 可以相遇的建筑 #2736 最大和查询