Maximum Balanced Subsequence Sum solution and explanation
7 more videos on this problem
Maximum Balanced Subsequence Sum | Super Detailed Video | DP Concepts & Qns-16 | Leetcode-2926codestorywithMIK · 1:19:01 · 18K views
2926. Maximum Balanced Subsequence Sum | Weekly Leetcode 370codingMohan · 39:28 · 2K views
【每日一题】LeetCode 2926. Maximum Balanced Subsequence SumHuifeng Guan · 38:30 · 507 views
2926. Maximum Balanced Subsequence Sum (Leetcode Hard)Programming Live with Larry · 32:53 · 408 views
Maximum Balanced Subsequence Sum | weekly-contest-370Rohit Satpute · 11:15 · 255 views
2926. Maximum Balanced Subsequence Sum || Leetcode Weekly Contest 370Ashish Kumar · 38:42 · 228 views
Day 44/75: Problem Name: Maximum Balanced Subsequence Sum | Leetcode | #75DaysHardLeetcodeCodeInsanity · 10:47 · 149 views
Leetcode 2926 Max Balanced Sub SequenceBrain Box · 22:31 · 48 views
The problem
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 everyjin 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.
def max_balanced_subsequence_sum(nums):
n = len(nums)
dp = [0] * n
max_sum = nums[0]
dp[0] = nums[0]
for i in range(1, n):
dp[i] = nums[i]
for j in range(i):
if nums[i] - nums[j] >= i - j:
dp[i] = max(dp[i], dp[j] + nums[i])
max_sum = max(max_sum, dp[i])
return max_sum
# Example usage:
print(max_balanced_subsequence_sum([3,3,5,6])) # Output: 14
print(max_balanced_subsequence_sum([5,-1,-3,8])) # Output: 13
print(max_balanced_subsequence_sum([-2,-1])) # Output: -1import java.util.*;
public class MaxBalancedSubsequence {
public static int maxBalancedSubsequenceSum(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
int maxSum = nums[0];
dp[0] = nums[0];
for (int i = 1; i < n; i++) {
dp[i] = nums[i];
for (int j = 0; j < i; j++) {
if (nums[i] - nums[j] >= i - j) {
dp[i] = Math.max(dp[i], dp[j] + nums[i]);
}
}
maxSum = Math.max(maxSum, dp[i]);
}
return maxSum;
}
public static void main(String[] args) {
int[] nums1 = {3, 3, 5, 6};
System.out.println(maxBalancedSubsequenceSum(nums1)); // Output: 14
int[] nums2 = {5, -1, -3, 8};
System.out.println(maxBalancedSubsequenceSum(nums2)); // Output: 13
int[] nums3 = {-2, -1};
System.out.println(maxBalancedSubsequenceSum(nums3)); // Output: -1
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int maxBalancedSubsequenceSum(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n);
int maxSum = nums[0];
dp[0] = nums[0];
for (int i = 1; i < n; ++i) {
dp[i] = nums[i];
for (int j = 0; j < i; ++j) {
if (nums[i] - nums[j] >= i - j) {
dp[i] = max(dp[i], dp[j] + nums[i]);
}
}
maxSum = max(maxSum, dp[i]);
}
return maxSum;
}
int main() {
vector<int> nums1 = {3, 3, 5, 6};
cout << "Output: " << maxBalancedSubsequenceSum(nums1) << endl;
vector<int> nums2 = {5, -1, -3, 8};
cout << "Output: " << maxBalancedSubsequenceSum(nums2) << endl;
vector<int> nums3 = {-2, -1};
cout << "Output: " << maxBalancedSubsequenceSum(nums3) << endl;
return 0;
}function maxBalancedSubsequenceSum(nums) {
let n = nums.length;
let dp = new Array(n).fill(0);
let maxSum = nums[0];
dp[0] = nums[0];
for (let i = 1; i < n; i++) {
dp[i] = nums[i];
for (let j = 0; j < i; j++) {
if (nums[i] - nums[j] >= i - j) {
dp[i] = Math.max(dp[i], dp[j] + nums[i]);
}
}
maxSum = Math.max(maxSum, dp[i]);
}
return maxSum;
}
// Example usage:
console.log(maxBalancedSubsequenceSum([3, 3, 5, 6])); // Output: 14
console.log(maxBalancedSubsequenceSum([5, -1, -3, 8])); // Output: 13
console.log(maxBalancedSubsequenceSum([-2, -1])); // Output: -1;#include <stdio.h>
#include <stdlib.h>
int maxBalancedSubsequenceSum(int* nums, int n) {
int* dp = (int*)malloc(n * sizeof(int));
int maxSum = nums[0];
dp[0] = nums[0];
for (int i = 1; i < n; ++i) {
dp[i] = nums[i];
for (int j = 0; j < i; ++j) {
if (nums[i] - nums[j] >= i - j) {
if (dp[i] < dp[j] + nums[i]) {
dp[i] = dp[j] + nums[i];
}
}
}
if (maxSum < dp[i]) {
maxSum = dp[i];
}
}
free(dp);
return maxSum;
}
int main() {
int nums1[] = {3, 3, 5, 6};
printf("Output: %d\n", maxBalancedSubsequenceSum(nums1, 4));
int nums2[] = {5, -1, -3, 8};
printf("Output: %d\n", maxBalancedSubsequenceSum(nums2, 4));
int nums3[] = {-2, -1};
printf("Output: %d\n", maxBalancedSubsequenceSum(nums3, 2));
return 0;
}using System;
public class MaxBalancedSubsequence {
public static int MaxBalancedSubsequenceSum(int[] nums) {
int n = nums.Length;
int[] dp = new int[n];
int maxSum = nums[0];
dp[0] = nums[0];
for (int i = 1; i < n; i++) {
dp[i] = nums[i];
for (int j = 0; j < i; j++) {
if (nums[i] - nums[j] >= i - j) {
dp[i] = Math.Max(dp[i], dp[j] + nums[i]);
}
}
maxSum = Math.Max(maxSum, dp[i]);
}
return maxSum;
}
public static void Main(string[] args) {
int[] nums1 = {3, 3, 5, 6};
Console.WriteLine(MaxBalancedSubsequenceSum(nums1)); // Output: 14
int[] nums2 = {5, -1, -3, 8};
Console.WriteLine(MaxBalancedSubsequenceSum(nums2)); // Output: 13
int[] nums3 = {-2, -1};
Console.WriteLine(MaxBalancedSubsequenceSum(nums3)); // Output: -1
}
}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.
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.
def max_balanced_subsequence_sum(nums):
nums.sort()
max_sum = float('-inf')
n = len(nums)
for start in range(n):
current_sum = nums[start]
last = start
for end in range(start + 1, n):
if nums[end] - nums[last] >= end - last:
current_sum += nums[end]
last = end
max_sum = max(max_sum, current_sum)
return max_sum
# Example usage
print(max_balanced_subsequence_sum([3,3,5,6])) # Output: 14
print(max_balanced_subsequence_sum([5,-1,-3,8])) # Output: 13
print(max_balanced_subsequence_sum([-2,-1])) # Output: -1#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int maxBalancedSubsequenceSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
int maxSum = INT_MIN;
int n = nums.size();
for (int start = 0; start < n; ++start) {
int currentSum = nums[start];
int last = start;
for (int end = start + 1; end < n; ++end) {
if (nums[end] - nums[last] >= end - last) {
currentSum += nums[end];
last = end;
}
}
maxSum = max(maxSum, currentSum);
}
return maxSum;
}
int main() {
vector<int> nums1 = {3, 3, 5, 6};
cout << "Output: " << maxBalancedSubsequenceSum(nums1) << endl;
vector<int> nums2 = {5, -1, -3, 8};
cout << "Output: " << maxBalancedSubsequenceSum(nums2) << endl;
vector<int> nums3 = {-2, -1};
cout << "Output: " << maxBalancedSubsequenceSum(nums3) << endl;
return 0;
}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 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$.
class BinaryIndexedTree {
private n: number;
private c: number[];
constructor(n: number) {
this.n = n;
this.c = Array(n + 1).fill(-Infinity);
}
update(x: number, v: number): void {
while (x <= this.n) {
this.c[x] = Math.max(this.c[x], v);
x += x & -x;
}
}
query(x: number): number {
let mx = -Infinity;
while (x > 0) {
mx = Math.max(mx, this.c[x]);
x -= x & -x;
}
return mx;
}
}
function maxBalancedSubsequenceSum(nums: number[]): number {
const n = nums.length;
const arr = Array(n).fill(0);
for (let i = 0; i < n; ++i) {
arr[i] = nums[i] - i;
}
arr.sort((a, b) => a - b);
let m = 0;
for (let i = 0; i < n; ++i) {
if (i === 0 || arr[i] !== arr[i - 1]) {
arr[m++] = arr[i];
}
}
arr.length = m;
const tree = new BinaryIndexedTree(m);
const search = (nums: number[], x: number): number => {
let [l, r] = [0, nums.length];
while (l < r) {
const mid = (l + r) >> 1;
if (nums[mid] >= x) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
};
for (let i = 0; i < n; ++i) {
const j = search(arr, nums[i] - i) + 1;
const v = Math.max(tree.query(j), 0) + nums[i];
tree.update(j, v);
}
return tree.query(m);
}const inf int = 1e18
type BinaryIndexedTree struct {
n int
c []int
}
func NewBinaryIndexedTree(n int) BinaryIndexedTree {
c := make([]int, n+1)
for i := range c {
c[i] = -inf
}
return BinaryIndexedTree{n: n, c: c}
}
func (bit *BinaryIndexedTree) update(x, v int) {
for x <= bit.n {
bit.c[x] = max(bit.c[x], v)
x += x & -x
}
}
func (bit *BinaryIndexedTree) query(x int) int {
mx := -inf
for x > 0 {
mx = max(mx, bit.c[x])
x -= x & -x
}
return mx
}
func maxBalancedSubsequenceSum(nums []int) int64 {
n := len(nums)
arr := make([]int, n)
for i, x := range nums {
arr[i] = x - i
}
sort.Ints(arr)
m := 0
for i, x := range arr {
if i == 0 || x != arr[i-1] {
arr[m] = x
m++
}
}
arr = arr[:m]
tree := NewBinaryIndexedTree(m)
for i, x := range nums {
j := sort.SearchInts(arr, x-i) + 1
v := max(tree.query(j), 0) + x
tree.update(j, v)
}
return int64(tree.query(m))
}Complexity comparison
| 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. |
| Dynamic Programming + Binary Indexed Tree | – |
Complexity analysis
| 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 |
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.