Problem Statement

You are given two 0-indexed arrays, prices and profits, both of length n. There are n items in an store where the i^th item has a price of prices[i] and a profit of profits[i].

You have to select three items with the following condition:

• prices[i] < prices[j] < prices[k] where i < j < k.
• If such a selection is possible, calculate the total profit, which is profits[i] + profits[j] + profits[k].

Return the maximum possible profit from this selection. If it's not possible to select three items that satisfy these conditions, return -1.

Examples

Example 1:

• Input: prices = [3, 1, 4, 6, 2], profits = [5, 2, 8, 10, 3]
• Expected Output: 23
• Explanation: The selected triplet is (3, 4, 6) with indices 0, 2, 3. The corresponding profits are 5 + 8 + 10 = 23.

Example 2:

• Input: prices = [2, 7, 1, 5, 8, 10], profits = [3, 9, 1, 4, 7, 6]
• Expected Output: 22
• Explanation: The selected triplet is (7, 8, 10) with indices 1, 4, 5. The corresponding profits are 9 + 7 + 6 = 22.

Example 3:

• Input: prices = [9, 8, 7, 6, 5], profits = [10, 9, 8, 7, 6]
• Expected Output: -1
• Explanation: It is not possible to select three items such that their prices strictly increase.

Constraints:

• 3 <= prices.length == profits.length <= 2000
• 1 <= prices[i] <= 10⁶
• 1 <= profits[i] <= 10⁶

Try it yourself

Try solving this question here: