Maximum Balanced Subsequence Sum — LeetCode 2926 Python Solution
HardBinary Indexed TreeSegment TreeArrayBinary SearchDynamic Programming
- Problem
- #2926
- Pattern
- Monotonic Stack
- Reading time
- 5 min
- Source
- leetcode.com
The problem
You are given a 0-indexed integer array nums. A subsequence of nums having length k and consisting of indices i0 < i1 < ...
Example
- 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.
Python solution
Python
class BinaryIndexedTree:
def __init__(self, n: int):
self.n = n
self.c = [-inf] * (n + 1)
def update(self, x: int, v: int):
while x <= self.n:
self.c[x] = max(self.c[x], v)
x += x & -x
def query(self, x: int) -> int:
mx = -inf
while x:
mx = max(mx, self.c[x])
x -= x & -x
return mx
class Solution:
def maxBalancedSubsequenceSum(self, nums: List[int]) -> int:
arr = [x - i for i, x in enumerate(nums)]
s = sorted(set(arr))
tree = BinaryIndexedTree(len(s))
for i, x in enumerate(nums):
j = bisect_left(s, x - i) + 1
v = max(tree.query(j), 0) + x
tree.update(j, v)
return tree.query(len(s))Complexity
| Measure | Complexity |
|---|---|
| Time | O(n \times \log n) |
| Space | O(n) auxiliary |
Pattern: Monotonic Stack
Answer "what is the next greater element" for every position in one pass. LeetCode 2926. Maximum Balanced Subsequence Sum is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.
The monotonic stack guide has the Python template for the pattern and the 225 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 2926. Maximum Balanced Subsequence Sum?
- LeetCode 2926. Maximum Balanced Subsequence Sum is rated Hard on LeetCode.
- What is the time complexity of LeetCode 2926. Maximum Balanced Subsequence Sum?
- The Python solution on this page runs in O(n \times \log n).
- What is the space complexity of LeetCode 2926. Maximum Balanced Subsequence Sum?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 2926. Maximum Balanced Subsequence Sum cover?
- LeetCode 2926. Maximum Balanced Subsequence Sum is tagged Binary Indexed Tree, Segment Tree, Array, Binary Search and Dynamic Programming on LeetCode.