Skip to main content
Talentd

Maximum Balanced Subsequence Sum - Solution & Explanation

HardArrayBinary SearchDynamic ProgrammingBinary Indexed Tree19 min readAsked at: Amazon
Practice this problem

Problem Statement

You are given a 0-indexed integer array nums.

A subsequence of nums having length k and consisting of indices i0 < i1 < ... < ik-1 is balanced if the following holds:

  • nums[ij] - nums[ij-1] >= ij - ij-1, for every j in the range [1, k - 1].

A subsequence of nums having length 1 is considered balanced.

Return an integer denoting the maximum possible sum of elements in a balanced subsequence of nums.

A subsequence of an array is a new non-empty array that is formed from the original array by deleting some (possibly none) of the elements without disturbing the relative positions of the remaining elements.

 

Example 1:

Input: nums = [3,3,5,6]
Output: 14
Explanation: 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
Explanation: 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
Explanation: 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

Approach Overview

Problem Overview: You are given an integer array nums. A subsequence is considered balanced if for every pair of chosen indices i < j, the condition nums[j] - nums[i] >= j - i holds. The goal is to select a subsequence that satisfies this rule while maximizing the total sum of its elements.

The key observation comes from rearranging the condition: nums[j] - j >= nums[i] - i. This converts the constraint into a monotonic ordering problem based on the transformed value nums[i] - i. Once transformed, the task becomes a dynamic programming problem where you extend subsequences whose transformed values are non‑decreasing.

Approach 1: Dynamic Programming + Binary Indexed Tree (O(n log n) time, O(n) space)

This is the optimal approach. Define dp[i] as the maximum balanced subsequence sum ending at index i. To extend a subsequence ending at j, the transformed value must satisfy nums[j] - j <= nums[i] - i. That means you need the maximum dp[j] among all earlier elements with smaller or equal transformed value. A Binary Indexed Tree or Segment Tree supports fast prefix maximum queries. First perform coordinate compression on all values of nums[i] - i. Then iterate through the array, query the maximum DP value for valid transformed indices, and update the tree with dp[i] = nums[i] + best_previous. This converts a quadratic DP into an efficient O(n log n) solution.

Approach 2: Greedy Ordering with Sorting + DP (O(n log n) time, O(n) space)

Another perspective treats the problem as selecting elements whose transformed values nums[i] - i form a non‑decreasing sequence. Compute this transformed value for each index and process candidates in sorted order. As you iterate, maintain the best achievable subsequence sum that can extend the current element. Sorting helps enforce the feasibility constraint, while DP tracks the optimal accumulation of values. This method still relies on efficient range maximum updates internally, so the complexity remains O(n log n). It is conceptually easier to reason about because the ordering constraint becomes explicit.

Both strategies rely on the same insight: rewriting the constraint converts the problem into a monotonic subsequence optimization. Instead of checking every pair of indices, you query previously computed states using efficient range queries.

Recommended for interviews: The dynamic programming solution with a Binary Indexed Tree is the expected approach. Interviewers want to see the algebraic transformation nums[i] - i and how it converts the constraint into a prefix maximum query problem. A brute force DP with O(n²) transitions shows the basic idea, but optimizing it with coordinate compression and a tree structure demonstrates strong knowledge of dynamic programming and advanced data structures.

Approach 1: Dynamic Programming Approach

In this approach, we use a dynamic programming array, dp[i], where each element stores the maximum sum of a balanced subsequence ending at the i-th element. We iterate through the array and for each element, check previous elements to find possible balanced subsequences ending at the current index. We update dp[i] by adding nums[i] to the maximum valid previous dp value.

This approach uses a dynamic programming array dp where each index computes the maximum sum of balanced subsequences ending up to that index. The nested loop inside the function checks every previous index to determine if adding the current number maintains the balance condition.

Code

PythonC++JavaCC#JavaScript

Python

C++

Java

C

C#

JavaScript

Complexity

Time Complexity: O(n^2) because of the nested loop for each element.
Space Complexity: O(n) due to the dp array storing the maximum sums.

Try this approach in the editor →

Approach 2: Greedy Approach with Sorting

This approach leverages sorting to efficiently determine the maximum balanced subsequence sum. By sorting the array based on potential subsequence contributions, we can select elements in a greedy manner while checking the balance condition. This reduces complexity significantly compared to a dynamic programming approach.

This method first sorts the array to simplify balance checks. We then iteratively extend subsequences starting from each index to ensure the sum is maximized while maintaining the required condition, evaluating new potential subsequences only if they maintain valid transitions.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(n^2) because of the inner loop for each starting index.
Space Complexity: O(1) as only a few additional variables are used.

Try this approach in the editor →

Approach 3: 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.

Suppose i is the index of the last element in the subsequence, then we consider the index j of the second to last element in the subsequence. If arr[j] \le arr[i], we can consider whether to add j to the subsequence.

Therefore, we define f[i] as the maximum sum of nums when the index of the last element in the subsequence is i. The answer is max_{i=0}^{n-1} f[i].

The state transition equation is:

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

where j satisfies arr[j] \le arr[i].

We can use a Binary Indexed Tree to maintain the maximum value of the prefix, i.e., for each arr[i], we maintain the maximum value of f[i] in the prefix arr[0..i].

The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the array nums$.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming Approach

Time Complexity: O(n^2) because of the nested loop for each element.
Space Complexity: O(n) due to the dp array storing the maximum sums.

Greedy Approach with Sorting

Time Complexity: O(n^2) because of the inner loop for each starting index.
Space Complexity: O(1) as only a few additional variables are used.

Dynamic Programming + Binary Indexed Tree—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Dynamic ProgrammingO(n^2)O(n)Useful for understanding the transition relation and verifying correctness on small inputs
Dynamic Programming + Binary Indexed TreeO(n log n)O(n)Best general solution for large arrays; supports fast prefix maximum queries
DP + Segment TreeO(n log n)O(n)Alternative to Fenwick Tree when implementing range maximum queries more explicitly
Greedy Ordering with Sorting + DPO(n log n)O(n)Useful when reasoning about transformed ordering of values nums[i] - i

Video Solution

Maximum Balanced Subsequence Sum | Super Detailed Video | DP Concepts & Qns-16 | Leetcode-2926 • codestorywithMIK • 18,369 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Maximum Balanced Subsequence Sum easy or hard?
Maximum Balanced Subsequence Sum is classified as Hard on LeetCode. The difficulty comes from recognizing the algebraic transformation nums[i] - i and combining dynamic programming with advanced data structures like Fenwick Trees or Segment Trees.
Maximum Balanced Subsequence Sum Python/Java solution
Python, Java, and C++ implementations typically use dynamic programming with coordinate compression and a Fenwick Tree for prefix maximum queries. Each iteration queries the best previous subsequence sum and updates the tree with the new DP value computed for the current index.
How to solve Maximum Balanced Subsequence Sum in O(n log n)?
Transform the constraint nums[j] - nums[i] >= j - i into nums[j] - j >= nums[i] - i. Use dynamic programming where dp[i] is the best subsequence sum ending at i. Perform coordinate compression on transformed values and use a Binary Indexed Tree to query the maximum dp value for all smaller or equal transformed values before updating with dp[i].
What is the best approach for Maximum Balanced Subsequence Sum?
The best approach uses dynamic programming with a Binary Indexed Tree (Fenwick Tree). After transforming each element to nums[i] - i, the problem becomes finding the maximum subsequence sum where transformed values are non‑decreasing. A Fenwick Tree efficiently stores prefix maximum DP values, producing an O(n log n) time solution.
Is Maximum Balanced Subsequence Sum asked at Google/Amazon/Meta?
Hard dynamic programming problems involving Fenwick Trees, coordinate compression, and subsequence optimization commonly appear in interviews at companies like Google, Amazon, and Meta. This problem tests recognition of mathematical transformations combined with efficient range queries.
What data structure is used in Maximum Balanced Subsequence Sum?
The optimal solution uses a Binary Indexed Tree (Fenwick Tree) or Segment Tree to maintain prefix maximum values of dynamic programming states. These structures allow efficient O(log n) queries and updates while processing the transformed array values.
What is the time complexity of Maximum Balanced Subsequence Sum?
The optimal solution runs in O(n log n) time and O(n) space. The log factor comes from Fenwick Tree or Segment Tree operations used to query the maximum DP value for all valid previous indices while processing the array.

Ready to solve this problem?

Practice Maximum Balanced Subsequence Sum with our built-in code editor and test cases.

Practice on FleetCode
Previous

Number of Pairs Satisfying Inequality