Leetcode Problem 2926. Maximum Balanced Subsequence Sum

2926. Maximum Balanced Subsequence Sum

Leetcode Solutions

nums[i] - i >= nums[j] - j

  1. Initialize a map m with a pair (INT_MIN, 0) to track the adjusted value and the maximum sum of a balanced subsequence ending with that value.
  2. Iterate through the array nums.
  3. For each element nums[i], calculate the adjusted value nums[i] - i.
  4. Find the largest key in the map m that is not greater than nums[i] - i using upper_bound.
  5. Calculate the new sum as nums[i] plus the second value of the found pair in the map (if any).
  6. Insert or update the pair (nums[i] - i, sum) in the map m.
  7. Remove all pairs from the map with a key larger than nums[i] - i and a sum smaller than sum.
  8. After iterating through all elements, return the second value of the last pair in the map m as the maximum sum of a balanced subsequence.
UML Thumbnail

Dynamic Programming with Binary Indexed Tree (Fenwick Tree)

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...