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] <= 109The key observation in #2926 Maximum Balanced Subsequence Sum is to rewrite the balance condition so that it becomes easier to compare elements in a subsequence. By rearranging the inequality, the constraint can be expressed using the transformed value nums[i] - i. A valid balanced subsequence must maintain a non‑decreasing order of this transformed value.
This allows us to frame the problem as a dynamic programming task where dp[i] represents the maximum subsequence sum ending at index i. For each element, we want the best previous dp[j] where (nums[j] - j) <= (nums[i] - i). To efficiently query the maximum value among valid candidates, we can use a Binary Indexed Tree or Segment Tree after applying coordinate compression on the transformed values.
Each step performs a range maximum query and an update with the new DP value, leading to an efficient solution suitable for large inputs. The optimized approach runs in O(n log n) time with O(n) additional space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming + Binary Indexed Tree | O(n log n) | O(n) |
| Dynamic Programming + Segment Tree | O(n log n) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Let <code>dp[x]</code> represent the maximum sum of a balanced subsequence ending at <code>x</code>.
Rewriting the formula <code>nums[i<sub>j</sub>] - nums[i<sub>j-1</sub>] >= i<sub>j</sub> - i<sub>j-1</sub></code> gives <code>nums[i<sub>j</sub>] - i<sub>j</sub> >= nums[i<sub>j-1</sub>] - i<sub>j-1</sub></code>.
So, for some index <code>x</code>, we need to find an index <code>y</code>, <code>y < x</code>, such that <code>dp[x] = nums[x] + dp[y]</code> is maximized, and <code>nums[x] - x >= nums[y] - y</code>.
There are many ways to achieve this. One method involves sorting the values of <code>nums[x] - x</code> for all indices <code>x</code> and using a segment/Fenwick tree with coordinate compression.
Hence, using a dictionary or map, let's call it <code>dict</code>, where <code>dict[nums[x] - x]</code> represents the position of the value, <code>nums[x] - x</code>, in the segment tree.
The tree is initialized with zeros initially.
For indices <code>x</code> in order from <code>[0, n - 1]</code>, <code>dp[x] = max(nums[x]</code>, <code>nums[x]</code> + the maximum query from the tree in the range <code>[0, dict[nums[x] - x]])</code>, and if <code>dp[x]</code> is greater than the value in the tree at position <code>dict[nums[x] - x]</code>, we update the value in the tree.
The answer to the problem is the maximum value in <code>dp</code>.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Rewriting the balance condition reveals that a valid subsequence requires the value nums[j] - j to be less than or equal to nums[i] - i. This transformation converts the constraint into an ordered comparison that can be handled efficiently with range queries.
Problems involving dynamic programming combined with advanced data structures like Fenwick Trees or Segment Trees are common in FAANG-style interviews. This question tests optimization, transformation of constraints, and efficient querying techniques.
A Binary Indexed Tree (Fenwick Tree) or a Segment Tree works best for this problem. Both support fast range maximum queries and updates, which are needed to compute the dynamic programming transitions efficiently.
The optimal solution transforms the constraint using the expression nums[i] - i and applies dynamic programming. A Binary Indexed Tree or Segment Tree is used to efficiently query the maximum DP value for valid previous elements. This reduces the time complexity to O(n log n).