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].

We have to pick three items with the following condition:

  • prices[i] < prices[j] < prices[k] where i < j < k.

If we pick items with indices i, j and k satisfying the above condition, the profit would be profits[i] + profits[j] + profits[k].

Return _themaximum profit we can get, and _-1 if it ’s not possible to pick three items with the given condition.

Examples

Example 1:

1
2
3
4
5

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.
So the only triplet we can pick, are the items with indices 1, 2 and 3 and it's a valid pick since prices[1] < prices[2] < prices[3].
The answer would be sum of their profits which is 2 + 7 + 10 = 19.

Example 2:

1
2
3
4
5

Input: prices = [1,2,3,4,5], profits = [1,5,3,4,6]
Output: 15
Explanation: We can select any triplet of items since for each triplet of indices i, j and k such that i < j < k, the condition holds.
Therefore the maximum profit we can get would be the 3 most profitable items which are indices 1, 3 and 4.
The answer would be sum of their profits which is 5 + 4 + 6 = 15.

Example 3:

1
2
3

Input: prices = [4,3,2,1], profits = [33,20,19,87]
Output: -1
Explanation: We can't select any triplet of indices such that the condition holds, so we return -1.

Constraints:

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

Solution

Method 1 – Brute Force with Three Nested Loops

Intuition

We want to find three indices i < j < k such that prices[i] < prices[j] < prices[k] and maximize profits[i] + profits[j] + profits[k]. The brute force way is to check all possible triplets.

Approach

  1. Iterate over all possible triplets (i, j, k) with i < j < k.
  2. For each triplet, check if prices[i] < prices[j] < prices[k].
  3. If valid, compute the sum of profits and update the maximum.
  4. Return the maximum profit found, or -1 if no valid triplet exists.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int maxProfit(vector<int>& prices, vector<int>& profits) {
        int n = prices.size(), ans = -1;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (prices[i] < prices[j]) {
                    for (int k = j + 1; k < n; ++k) {
                        if (prices[j] < prices[k]) {
                            int sum = profits[i] + profits[j] + profits[k];
                            if (sum > ans) ans = sum;
                        }
                    }
                }
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func maxProfit(prices []int, profits []int) int {
    n, ans := len(prices), -1
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            if prices[i] < prices[j] {
                for k := j + 1; k < n; k++ {
                    if prices[j] < prices[k] {
                        sum := profits[i] + profits[j] + profits[k]
                        if sum > ans {
                            ans = sum
                        }
                    }
                }
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public int maxProfit(int[] prices, int[] profits) {
        int n = prices.length, ans = -1;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (prices[i] < prices[j]) {
                    for (int k = j + 1; k < n; k++) {
                        if (prices[j] < prices[k]) {
                            int sum = profits[i] + profits[j] + profits[k];
                            if (sum > ans) ans = sum;
                        }
                    }
                }
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun maxProfit(prices: IntArray, profits: IntArray): Int {
        val n = prices.size
        var ans = -1
        for (i in 0 until n) {
            for (j in i + 1 until n) {
                if (prices[i] < prices[j]) {
                    for (k in j + 1 until n) {
                        if (prices[j] < prices[k]) {
                            val sum = profits[i] + profits[j] + profits[k]
                            if (sum > ans) ans = sum
                        }
                    }
                }
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def maxProfit(self, prices: list[int], profits: list[int]) -> int:
        n = len(prices)
        ans = -1
        for i in range(n):
            for j in range(i + 1, n):
                if prices[i] < prices[j]:
                    for k in range(j + 1, n):
                        if prices[j] < prices[k]:
                            s = profits[i] + profits[j] + profits[k]
                            if s > ans:
                                ans = s
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

impl Solution {
    pub fn max_profit(prices: Vec<i32>, profits: Vec<i32>) -> i32 {
        let n = prices.len();
        let mut ans = -1;
        for i in 0..n {
            for j in i+1..n {
                if prices[i] < prices[j] {
                    for k in j+1..n {
                        if prices[j] < prices[k] {
                            let sum = profits[i] + profits[j] + profits[k];
                            if sum > ans {
                                ans = sum;
                            }
                        }
                    }
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    maxProfit(prices: number[], profits: number[]): number {
        const n = prices.length;
        let ans = -1;
        for (let i = 0; i < n; i++) {
            for (let j = i + 1; j < n; j++) {
                if (prices[i] < prices[j]) {
                    for (let k = j + 1; k < n; k++) {
                        if (prices[j] < prices[k]) {
                            const sum = profits[i] + profits[j] + profits[k];
                            if (sum > ans) ans = sum;
                        }
                    }
                }
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^3), where n is the number of items. We check all possible triplets.
  • 🧺 Space complexity: O(1), only a constant number of variables are used.