Maximum Profitable Triplets With Increasing Prices I — LeetCode 2907 Python Solution
MediumLeetCode PremiumBinary Indexed TreeSegment TreeArray
- Problem
- #2907
- 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
Python
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
| Measure | Complexity |
|---|---|
| Time | O(n^2), where n is the length of the array |
| Space | O(1) auxiliary |
Related problems
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(n^2), 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.