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] <= 109Problem 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.
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.
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.
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.
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.
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n^2) because of the nested loop for each element. |
| Greedy Approach with Sorting | Time Complexity: O(n^2) because of the inner loop for each starting index. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Dynamic Programming | O(n^2) | O(n) | Useful for understanding the transition relation and verifying correctness on small inputs |
| Dynamic Programming + Binary Indexed Tree | O(n log n) | O(n) | Best general solution for large arrays; supports fast prefix maximum queries |
| DP + Segment Tree | O(n log n) | O(n) | Alternative to Fenwick Tree when implementing range maximum queries more explicitly |
| Greedy Ordering with Sorting + DP | O(n log n) | O(n) | Useful when reasoning about transformed ordering of values nums[i] - i |
Maximum Balanced Subsequence Sum | Super Detailed Video | DP Concepts & Qns-16 | Leetcode-2926 • codestorywithMIK • 15,341 views views
Watch 7 more video solutions →Practice Maximum Balanced Subsequence Sum with our built-in code editor and test cases.
Practice on FleetCode