#2926

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Maximum Balanced Subsequence Sum

Learn to find the maximum sum of a balanced subsequence using dynamic programming and careful state transitions efficiently.

array binary search dynamic programming binary indexed tree segment tree

Problem Statement

Given a 0-indexed integer array nums, determine the maximum sum of a subsequence that is balanced. A balanced subsequence must satisfy that for any two consecutive indices i and j in the subsequence, nums[j] - nums[i] >= j - i.

A subsequence of length 1 is automatically considered balanced. Your goal is to select indices i0 < i1 < ... < ik-1 to maximize the sum of nums[i0] + nums[i1] + ... + nums[ik-1] under the balance condition. The array can have up to 10^5 elements, and values can be large positive or negative integers.

Examples

Example 1

Input: nums = [3,3,5,6]

Output: 14

In this example, the subsequence [3,5,6] consisting of indices 0, 2, and 3 can be selected. nums[2] - nums[0] >= 2 - 0. nums[3] - nums[2] >= 3 - 2. Hence, it is a balanced subsequence, and its sum is the maximum among the balanced subsequences of nums. The subsequence consisting of indices 1, 2, and 3 is also valid. It can be shown that it is not possible to get a balanced subsequence with a sum greater than 14.

Example 2

Input: nums = [5,-1,-3,8]

Output: 13

In this example, the subsequence [5,8] consisting of indices 0 and 3 can be selected. nums[3] - nums[0] >= 3 - 0. Hence, it is a balanced subsequence, and its sum is the maximum among the balanced subsequences of nums. It can be shown that it is not possible to get a balanced subsequence with a sum greater than 13.

Example 3

Input: nums = [-2,-1]

Output: -1

In this example, the subsequence [-1] can be selected. It is a balanced subsequence, and its sum is the maximum among the balanced subsequences of nums.

Constraints

1 <= nums.length <= 105
-109 <= nums[i] <= 109

Solution Approach

Dynamic Programming with State Transition

Define dp[x] as the maximum sum of a balanced subsequence ending at index x. Iterate through the array, and for each nums[x], check all previous valid indices y where nums[x] - nums[y] >= x - y to update dp[x] = max(dp[x], dp[y] + nums[x]). Track the global maximum.

Optimization Using Binary Indexed Tree or Segment Tree

To avoid O(n^2) iterations, maintain a data structure that queries the maximum dp[y] for all y where the balance condition holds. Segment trees or binary indexed trees can store dp values keyed by adjusted indices to support efficient range maximum queries.

Binary Search for Valid Predecessors

Sort candidate indices with their adjusted values and use binary search to find predecessors y that satisfy nums[x] - nums[y] >= x - y. Update dp[x] using the best predecessor sum efficiently while scanning the array.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Naive DP has O(n^2) time due to checking all previous indices. Using segment trees or binary indexed trees reduces it to O(n log n) time. Space complexity is O(n) for dp and the auxiliary structures.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Dynamic Programming + Binary Indexed Tree

According to the problem description, we can transform the inequality $nums[i] - nums[j] \ge i - j$ into $nums[i] - i \ge nums[j] - j$. Therefore, we consider defining a new array $arr$, where $arr[i] = nums[i] - i$. A balanced subsequence satisfies that for any $j < i$, $arr[j] \le arr[i]$. The problem is transformed into selecting an increasing subsequence in $arr$ such that the corresponding sum in $nums$ is maximized.

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

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))

Continue Practicing

#2916 subarrays distinct element sum of squares ii #2940 find building where alice and bob can meet #2736 maximum sum queries