2926. Maximum Balanced Subsequence Sum LeetCode Solution

Last updated: March 5, 2025

In this guide, you will get 2926. Maximum Balanced Subsequence Sum LeetCode Solution with the best time and space complexity. The solution to Maximum Balanced Subsequence Sum problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Maximum Balanced Subsequence Sum solution in C++
Maximum Balanced Subsequence Sum solution in Java
Maximum Balanced Subsequence Sum solution in Python
Additional Resources

2926. Maximum Balanced Subsequence Sum LeetCode Solution image

Problem Statement of Maximum Balanced Subsequence Sum

You are given a 0-indexed integer array nums.
A subsequence of nums having length k and consisting of indices i0 < i1 < … = 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] <= 109

Complexity Analysis

Time Complexity: O(n\log n)
Space Complexity: O(n)

2926. Maximum Balanced Subsequence Sum LeetCode Solution in C++

class FenwickTree {
 public:
  FenwickTree(int n) : vals(n + 1) {}

  // Updates the maximum sum of subsequence ending in (i - 1) with `val`.
  void maximize(int i, long val) {
    while (i < vals.size()) {
      vals[i] = max(vals[i], val);
      i += lowbit(i);
    }
  }

  // Returns the maximum sum of subsequence ending in (i - 1).
  long get(int i) const {
    long res = 0;
    while (i > 0) {
      res = max(res, vals[i]);
      i -= lowbit(i);
    }
    return res;
  }

 private:
  vector<long> vals;

  static int lowbit(int i) {
    return i & -i;
  }
};

class Solution {
 public:
  long long maxBalancedSubsequenceSum(vector<int>& nums) {
    // Let's define maxSum[i] := subsequence with the maximum sum ending in i
    // By observation:
    //     nums[i] - nums[j] >= i - j
    //  => nums[i] - i >= nums[j] - j
    //  So, if nums[i] - i >= nums[j] - j, where i > j,
    //  maxSum[i] = max(maxSum[i], maxSum[j] + nums[i])
    long ans = LONG_MIN;
    FenwickTree tree(nums.size());

    for (const auto& [_, i] : getPairs(nums)) {
      const long subseqSum = tree.get(i) + nums[i];
      tree.maximize(i + 1, subseqSum);
      ans = max(ans, subseqSum);
    }

    return ans;
  }

 private:
  vector<pair<int, int>> getPairs(const vector<int>& nums) {
    vector<pair<int, int>> pairs;
    for (int i = 0; i < nums.size(); ++i)
      pairs.emplace_back(nums[i] - i, i);
    ranges::sort(pairs);
    return pairs;
  }
};
/* code provided by PROGIEZ */

2926. Maximum Balanced Subsequence Sum LeetCode Solution in Java

class FenwickTree {
  public FenwickTree(int n) {
    vals = new long[n + 1];
  }

  // Updates the maximum sum of subsequence ending in (i - 1) with `val`.
  public void maximize(int i, long val) {
    while (i < vals.length) {
      vals[i] = Math.max(vals[i], val);
      i += lowbit(i);
    }
  }

  // Returns the maximum sum of subsequence ending in (i - 1).
  public long get(int i) {
    long res = 0;
    while (i > 0) {
      res = Math.max(res, vals[i]);
      i -= lowbit(i);
    }
    return res;
  }

  private long[] vals;

  private static int lowbit(int i) {
    return i & -i;
  }
}

class Solution {
  public long maxBalancedSubsequenceSum(int[] nums) {
    // Let's define maxSum[i] := subsequence with the maximum sum ending in i
    // By observation:
    //     nums[i] - nums[j] >= i - j
    //  => nums[i] - i >= nums[j] - j
    //  So, if nums[i] - i >= nums[j] - j, where i > j,
    //  maxSum[i] = max(maxSum[i], maxSum[j] + nums[i])
    long ans = Long.MIN_VALUE;
    FenwickTree tree = new FenwickTree(nums.length);

    for (Pair<Integer, Integer> pair : getPairs(nums)) {
      final int i = pair.getValue();
      final long subseqSum = tree.get(i) + nums[i];
      tree.maximize(i + 1, subseqSum);
      ans = Math.max(ans, subseqSum);
    }

    return ans;
  }

  private List<Pair<Integer, Integer>> getPairs(int[] nums) {
    List<Pair<Integer, Integer>> pairs = new ArrayList<>();
    for (int i = 0; i < nums.length; ++i)
      pairs.add(new Pair<>(nums[i] - i, i));
    pairs.sort((p1, p2) -> p1.getKey() - p2.getKey());
    return pairs;
  }
}
// code provided by PROGIEZ

2926. Maximum Balanced Subsequence Sum LeetCode Solution in Python

class FenwickTree:
  def __init__(self, n: int):
    self.vals = [0] * (n + 1)

  def maximize(self, i: int, val: int) -> None:
    """Updates the maximum sum of subsequence ending in (i - 1) with `val`."""
    while i < len(self.vals):
      self.vals[i] = max(self.vals[i], val)
      i += FenwickTree.lowbit(i)

  def get(self, i: int) -> int:
    """Returns the maximum sum of subsequence ending in (i - 1)."""
    res = 0
    while i > 0:
      res = max(res, self.vals[i])
      i -= FenwickTree.lowbit(i)
    return res

  @staticmethod
  def lowbit(i: int) -> int:
    return i & -i


class Solution:
  def maxBalancedSubsequenceSum(self, nums: list[int]) -> int:
    # Let's define maxSum[i] := subsequence with the maximum sum ending in i
    # By observation:
    #    nums[i] - nums[j] >= i - j
    # => nums[i] - i >= nums[j] - j
    # So, if nums[i] - i >= nums[j] - j, where i > j,
    # maxSum[i] = max(maxSum[i], maxSum[j] + nums[i])
    ans = -math.inf
    tree = FenwickTree(len(nums))

    for _, i in sorted([(num - i, i) for i, num in enumerate(nums)]):
      subseqSum = tree.get(i) + nums[i]
      tree.maximize(i + 1, subseqSum)
      ans = max(ans, subseqSum)

    return ans
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents