Maximum Balanced Subsequence Sum

Maximum Balanced Subsequence Sum

What is this problem about?

You are given an integer array nums. A subsequence is considered "balanced" if, for every adjacent pair of elements nums[i] and nums[j] in the subsequence (where $i < j$), the condition nums[j] - nums[i] >= j - i holds true. Your goal is to find the maximum possible sum of any balanced subsequence.

Why is this asked in interviews?

This is a Hard-level Dynamic Programming problem that masks a beautiful mathematical trick. Interviewers ask it to separate candidates who write $O(N^2)$ standard LIS (Longest Increasing Subsequence) templates from those who can algebraically manipulate the constraint. It tests your ability to use advanced data structures like Segment Trees or Binary Indexed Trees (BIT) to optimize DP lookups.

Algorithmic pattern used

This relies on Algebraic Rearrangement and a Segment Tree / BIT for DP Optimization.

1. Rearrange the condition: nums[j] - nums[i] >= j - i translates perfectly to nums[j] - j >= nums[i] - i.
2. Let's define a new value for every element: val[i] = nums[i] - i. The problem is now identical to finding the Maximum Sum Increasing Subsequence based on this new val array! (You can only append nums[j] to nums[i] if val[j] >= val[i]).
3. Because we want the maximum sum (using nums[i]), standard $O(N^2)$ DP is too slow. We compress/sort the unique vals and use a Segment Tree or BIT. The tree will store the maximum sum achievable for a given val. We query the tree for the max sum of all values $\le val[i]$, add nums[i] (if it's positive), and update the tree.

Example explanation

Array nums = [3, 3, 5, 6]

1. Calculate val[i] = nums[i] - i:
   • idx 0: $3 - 0 = 3$.
   • idx 1: $3 - 1 = 2$.
   • idx 2: $5 - 2 = 3$.
   • idx 3: $6 - 3 = 3$. val array: [3, 2, 3, 3].
2. Iterate and use DP/BIT to find max sum where val[i] >= val[prev]:
   • num=3, val=3: Max sum $\le 3$ is 0. New sum = 3. Update tree at 3 with 3.
   • num=3, val=2: Max sum $\le 2$ is 0. New sum = 3. Update tree at 2 with 3.
   • num=5, val=3: Max sum $\le 3$ is 3 (from the first 3). New sum = $3 + 5 = 8$. Update tree at 3 with 8.
   • num=6, val=3: Max sum $\le 3$ is 8 (from the 5). New sum = $8 + 6 = 14$. Update tree at 3 with 14. The maximum balanced subsequence sum is 14 ([3, 5, 6]).

Common mistakes candidates make

The most critical mistake is failing to rearrange the inequality. If you leave it as nums[j] - nums[i] >= j - i, the dependencies are tangled, and you are forced into an $O(N^2)$ loop. Decoupling the j terms from the i terms is the only way to enable logarithmic data structures. Another mistake is including negative numbers in the sequence; if nums[i] is negative, it only hurts the sum, so it should be skipped unless the array is entirely negative (in which case, just return the max single negative element).

Interview preparation tip

When an interview problem gives you a constraint inequality involving two different array indices like A[j] - A[i] >= B[j] - B[i], always group the terms by index. Rewrite it as A[j] - B[j] >= A[i] - B[i]. This isolates the property to a single element, transforming an $O(N^2)$ pairwise relationship into a much simpler $O(N \log N)$ sorting or tree-based property check.