Max Profit Triplet
MediumArrays · SalesForce
A store lists n items in a fixed order. Item i has price prices[i] and profit profits[i].
Choose three indices i < j < k such that the prices strictly increase: prices[i] < prices[j] < prices[k]. The profit of the choice is profits[i] + profits[j] + profits[k].
Return the maximum profit over all valid choices, or -1 if no three items have strictly increasing prices in index order.
Example 1
- Input:
- prices = [6, 2, 9, 4, 7, 5], profits = [3, 8, 1, 6, 5, 9]
- Output:
- 23
- Explanation
- Valid choices include prices
2, 4, 7(profit8 + 6 + 5 = 19) and prices2, 4, 5(profit8 + 6 + 9 = 23). Nothing comes after the9, so no choice beats23.
Example 2
- Input:
- prices = [5, 4, 3], profits = [10, 20, 30]
- Output:
- -1
- Explanation
- Prices only decrease from left to right, so no valid choice exists.
Example 3
- Input:
- prices = [1, 3, 3, 5], profits = [2, 10, 20, 1]
- Output:
- 23
- Explanation
- Prices must strictly increase, so the two items priced
3cannot be chosen together. The best is1, 3, 5using the second3:2 + 20 + 1 = 23.
Constraints
- 1 ≤
n==prices.length==profits.length≤ 105 - 1 ≤
prices[i]≤ 109 - 1 ≤
profits[i]≤ 109