MediumNo. 2907LeetCode Premium
Maximum Profitable Triplets With Increasing Prices I — LeetCode 2907 Python Solution
- Topics
- Binary Indexed Tree, Segment Tree, Array
- Reading time
- 3 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 Solution:
def maxProfit(self, prices: List[int], profits: List[int]) -> int:
n = len(prices)
ans = -1
for j, x in enumerate(profits):
left = right = 0
for i in range(j):
if prices[i] < prices[j] and left < profits[i]:
left = profits[i]
for k in range(j + 1, n):
if prices[j] < prices[k] and right < profits[k]:
right = profits[k]
if left and right:
ans = max(ans, left + x + right)
return ansComplexity
- Time
- O(n2)where n is the length of the array
- Space · auxiliary
- O(1)
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0699 | Falling Squares | Hard |
| 0850 | Rectangle Area II | Hard |
| 2569 | Handling Sum Queries After Update | Hard |
| 2908 | Minimum Sum of Mountain Triplets I | Easy |
| 2909 | Minimum Sum of Mountain Triplets II | Medium |
| 0057 | Insert Interval | Medium |
Frequently asked questions
- How hard is LeetCode 2907. Maximum Profitable Triplets With Increasing Prices I?
LeetCode 2907. Maximum Profitable Triplets With Increasing Prices I is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2907. Maximum Profitable Triplets With Increasing Prices I?
The Python solution on this page runs in O(n2), where n is the length of the array.
- What is the space complexity of LeetCode 2907. Maximum Profitable Triplets With Increasing Prices I?
The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 2907. Maximum Profitable Triplets With Increasing Prices I cover?
LeetCode 2907. Maximum Profitable Triplets With Increasing Prices I is tagged Binary Indexed Tree, Segment Tree and Array on LeetCode.
- Is LeetCode 2907. Maximum Profitable Triplets With Increasing Prices I a premium problem?
Yes. LeetCode 2907. Maximum Profitable Triplets With Increasing Prices I is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.