HardNo. 2921LeetCode Premium
Maximum Profitable Triplets With Increasing Prices II — LeetCode 2921 Python Solution
- Topics
- Binary Indexed Tree, Segment Tree, Array
- Reading time
- 7 min
- Source
- leetcode.com
The problem
Given the 0-indexed arrays prices and profits of length n. There are n items in an store where the ith item has a price of prices[i] and a profit of profits[i].
Example
- Input
- prices = [10,2,3,4], profits = [100,2,7,10]
- Output
- 19
- Explanation
- We can't pick the item with index i=0 since there are no indices j and k such that the condition holds.
Python solution
class BinaryIndexedTree:
def __init__(self, n: int):
self.n = n
self.c = [0] * (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 = 0
while x:
mx = max(mx, self.c[x])
x -= x & -x
return mx
class Solution:
def maxProfit(self, prices: List[int], profits: List[int]) -> int:
n = len(prices)
left = [0] * n
right = [0] * n
m = max(prices)
tree1 = BinaryIndexedTree(m + 1)
tree2 = BinaryIndexedTree(m + 1)
for i, x in enumerate(prices):
left[i] = tree1.query(x - 1)
tree1.update(x, profits[i])
for i in range(n - 1, -1, -1):
x = m + 1 - prices[i]
right[i] = tree2.query(x - 1)
tree2.update(x, profits[i])
return max(
(l + x + r for l, x, r in zip(left, profits, right) if l and r), default=-1
)Complexity
- Time
- O(n × log M)
- Space · auxiliary
- O(M)
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0699 | Falling Squares | Hard |
| 0850 | Rectangle Area II | Hard |
| 2569 | Handling Sum Queries After Update | Hard |
| 0057 | Insert Interval | Medium |
| 0228 | Summary Ranges | Easy |
| 0485 | Max Consecutive Ones | Easy |
Frequently asked questions
- How hard is LeetCode 2921. Maximum Profitable Triplets With Increasing Prices II?
LeetCode 2921. Maximum Profitable Triplets With Increasing Prices II is rated Hard on LeetCode.
- What is the time complexity of LeetCode 2921. Maximum Profitable Triplets With Increasing Prices II?
The Python solution on this page runs in O(n × log M).
- What is the space complexity of LeetCode 2921. Maximum Profitable Triplets With Increasing Prices II?
The Python solution on this page uses O(M) auxiliary space.
- What topics does LeetCode 2921. Maximum Profitable Triplets With Increasing Prices II cover?
LeetCode 2921. Maximum Profitable Triplets With Increasing Prices II is tagged Binary Indexed Tree, Segment Tree and Array on LeetCode.
- Is LeetCode 2921. Maximum Profitable Triplets With Increasing Prices II a premium problem?
Yes. LeetCode 2921. Maximum Profitable Triplets With Increasing Prices II is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.