Leetcode Problem 2921. Maximum Profitable Triplets With Increasing Prices II

2921. Maximum Profitable Triplets With Increasing Prices II

Leetcode Solutions

Fenwick Tree + Dynamic Programming

  1. Initialize two Fenwick Trees (arrays), l1 and l2, to keep track of the maximum profit for 1-price and 2-price sequences respectively.
  2. Iterate through each item in prices and profits.
  3. For the current price, use the Fenwick Tree to query the maximum profit for any price less than the current price (1-price sequence).
  4. Update l1 with the current profit if it's higher than the existing profit for the current price.
  5. If there is a profit for a 1-price sequence, use it to update l2 with the sum of the current profit and the profit from the 1-price sequence (2-price sequence).
  6. Query l2 for the maximum profit of a 2-price sequence for any price less than the current price and add the current profit to check if it results in a higher overall profit.
  7. Keep track of the maximum profit found so far.
  8. Return the maximum profit or -1 if no valid triplet is found.
UML Thumbnail

Prefix and Suffix Maximum Profit Arrays

Ask Question

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

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...