Maximum Balanced Subsequence Sum - Practice Coding Problems

Maximum Balanced Subsequence Sum - Problem

You are given a 0-indexed integer array nums. A subsequence of nums having length k and consisting of indices i₀ < i₁ < ... < iₖ₋₁ is balanced if the following holds:

nums[iⱼ] - nums[iⱼ₋₁] >= iⱼ - iⱼ₋₁, 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.

Input & Output

Example 1 — Basic Balanced Subsequence

$ Input: nums = [3,4,5,1]

› Output: 12

💡 Note: The balanced subsequence [3,4,5] at indices [0,1,2] gives maximum sum. Check: 4-3 ≥ 1-0 (1≥1 ✓), 5-4 ≥ 2-1 (1≥1 ✓). Sum = 3+4+5 = 12.

Example 2 — Single Element Maximum

$ Input: nums = [-1,-2,-3]

› Output: -1

💡 Note: All single elements are balanced. The maximum single element is -1, so return -1.

Example 3 — Non-consecutive Subsequence

$ Input: nums = [5,-1,-3,8]

› Output: 13

💡 Note: The balanced subsequence [5,8] at indices [0,3] gives maximum sum. Check: 8-5 ≥ 3-0 (3≥3 ✓). Sum = 5+8 = 13.

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁹ ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array [3,4,5,1] with indices [0,1,2,3]

Check Balance

For subsequence to be balanced: nums[j] - nums[j-1] ≥ j - (j-1)

Find Maximum

Among all balanced subsequences, return maximum sum

Key Takeaway

🎯 Key Insight: Transform the balance condition to nums[i] - i ≥ nums[j] - j for efficient DP solution

Asked in

G Google 25 M Microsoft 20 a Amazon 15 f Meta 12

The key insight is to transform the balance condition by rearranging terms to nums[i] - i ≥ nums[j] - j. This allows us to use dynamic programming with coordinate compression and Binary Indexed Tree for efficient range maximum queries. Best approach achieves O(n log n) time and O(n) space.

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming	O(n²)	O(n)	Use DP to track maximum sum ending at each position
Coordinate Compression + Binary Indexed Tree	O(n log n)	O(n)	Optimize DP with coordinate compression and BIT for range maximum queries
Brute Force - Check All Subsequences	O(2ⁿ × n)	O(n)	Generate all possible subsequences and check balance condition

Dynamic Programming — Algorithm Steps

Transform condition: nums[i] - i ≥ nums[j] - j
Use DP where dp[i] = max sum ending at index i
For each position, find best previous position to extend from

Visualization

Tap to expand

Step-by-Step Walkthrough

Transform

Convert to nums[i] - i for easier comparison

DP Build

For each position, find best previous position to extend

Result

Return maximum value from all positions

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

long long solution(int* nums, int n) {
    if (n == 0) return 0;
    
    // Transform values: nums[i] - i
    long long transformed[1000];
    for (int i = 0; i < n; i++) {
        transformed[i] = nums[i] - i;
    }
    
    // dp[i] = maximum sum of balanced subsequence ending at index i
    long long dp[1000];
    for (int i = 0; i < n; i++) {
        dp[i] = nums[i];
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            // Check balance condition: transformed[i] >= transformed[j]
            if (transformed[i] >= transformed[j]) {
                long long newVal = dp[j] + nums[i];
                if (newVal > dp[i]) {
                    dp[i] = newVal;
                }
            }
        }
    }
    
    long long result = dp[0];
    for (int i = 1; i < n; i++) {
        if (dp[i] > result) result = dp[i];
    }
    
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000], n = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    long long result = solution(nums, n);
    printf("%lld\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Nested loops to check all pairs of positions

⚠ Quadratic Growth

Space Complexity

O(n)

DP array to store maximum sum at each position

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~35 min Avg. Time

342 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler