Maximum Profitable Triplets With Increasing Prices II

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 <= 50000
1 <= prices[i] <= 5000
1 <= profits[i] <= 10^6

Solution

Method 1 – Efficient DP with Segment Tree or Binary Indexed Tree

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]. Unlike the brute force approach, we can use dynamic programming and segment trees (or BIT) to efficiently find the best left and right profits for each middle index.

Approach

Coordinate compress the prices to allow efficient indexing in segment trees/BIT.
For each index j, find the maximum profit for a valid i < j with prices[i] < prices[j] (left best) and for k > j with prices[k] > prices[j] (right best).
Use a segment tree/BIT to maintain and query the best profit for left and right efficiently.
For each j, if both left and right exist, update the answer with left + profits[j] + right.
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
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


class Solution {
public:
    int maxProfit(vector<int>& prices, vector<int>& profits) {
        int n = prices.size();
        vector<int> sorted = prices;
        sort(sorted.begin(), sorted.end());
        sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
        auto get = [&](int x) {
            return lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin();
        };
        int m = sorted.size();
        vector<int> left(n, -1), right(n, -1);
        vector<int> bit(m + 2, -1);
        auto update = [&](int i, int val) {
            for (++i; i < bit.size(); i += i & -i) bit[i] = max(bit[i], val);
        };
        auto query = [&](int i) {
            int res = -1;
            for (++i; i > 0; i -= i & -i) res = max(res, bit[i]);
            return res;
        };
        for (int j = 0; j < n; ++j) {
            left[j] = query(get(prices[j]) - 1);
            update(get(prices[j]), profits[j]);
        }
        fill(bit.begin(), bit.end(), -1);
        for (int j = n - 1; j >= 0; --j) {
            right[j] = query(m - get(prices[j]) - 2);
            update(m - get(prices[j]) - 1, profits[j]);
        }
        int ans = -1;
        for (int j = 0; j < n; ++j) {
            if (left[j] != -1 && right[j] != -1) {
                ans = max(ans, left[j] + profits[j] + right[j]);
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70


func maxProfit(prices []int, profits []int) int {
    n := len(prices)
    sorted := append([]int{}, prices...)
    sort.Ints(sorted)
    uniq := []int{}
    for _, v := range sorted {
        if len(uniq) == 0 || uniq[len(uniq)-1] != v {
            uniq = append(uniq, v)
        }
    }
    get := func(x int) int {
        l, r := 0, len(uniq)
        for l < r {
            m := (l + r) / 2
            if uniq[m] < x {
                l = m + 1
            } else {
                r = m
            }
        }
        return l
    }
    m := len(uniq)
    left := make([]int, n)
    right := make([]int, n)
    for i := range left {
        left[i], right[i] = -1, -1
    }
    bit := make([]int, m+2)
    for i := range bit {
        bit[i] = -1
    }
    update := func(i, val int) {
        for i++; i < len(bit); i += i & -i {
            if val > bit[i] {
                bit[i] = val
            }
        }
    }
    query := func(i int) int {
        res := -1
        for i++; i > 0; i -= i & -i {
            if bit[i] > res {
                res = bit[i]
            }
        }
        return res
    }
    for j := 0; j < n; j++ {
        left[j] = query(get(prices[j]) - 1)
        update(get(prices[j]), profits[j])
    }
    for i := range bit {
        bit[i] = -1
    }
    for j := n - 1; j >= 0; j-- {
        right[j] = query(m - get(prices[j]) - 2)
        update(m - get(prices[j]) - 1, profits[j])
    }
    ans := -1
    for j := 0; j < n; j++ {
        if left[j] != -1 && right[j] != -1 {
            sum := left[j] + profits[j] + right[j]
            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
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


class Solution {
    public int maxProfit(int[] prices, int[] profits) {
        int n = prices.length;
        int[] sorted = prices.clone();
        Arrays.sort(sorted);
        int m = 0;
        for (int i = 0; i < n; i++) if (m == 0 || sorted[m-1] != sorted[i]) sorted[m++] = sorted[i];
        int[] left = new int[n], right = new int[n];
        Arrays.fill(left, -1); Arrays.fill(right, -1);
        int[] bit = new int[m+2];
        Arrays.fill(bit, -1);
        for (int j = 0; j < n; j++) {
            int idx = Arrays.binarySearch(sorted, 0, m, prices[j]);
            int l = idx;
            int best = -1;
            for (int i = l; i > 0; i -= i & -i) best = Math.max(best, bit[i]);
            left[j] = best;
            for (int i = l+1; i < bit.length; i += i & -i) bit[i] = Math.max(bit[i], profits[j]);
        }
        Arrays.fill(bit, -1);
        for (int j = n-1; j >= 0; j--) {
            int idx = Arrays.binarySearch(sorted, 0, m, prices[j]);
            int l = m - idx - 1;
            int best = -1;
            for (int i = l; i > 0; i -= i & -i) best = Math.max(best, bit[i]);
            right[j] = best;
            for (int i = l+1; i < bit.length; i += i & -i) bit[i] = Math.max(bit[i], profits[j]);
        }
        int ans = -1;
        for (int j = 0; j < n; j++) {
            if (left[j] != -1 && right[j] != -1) {
                ans = Math.max(ans, left[j] + profits[j] + right[j]);
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43


class Solution {
    fun maxProfit(prices: IntArray, profits: IntArray): Int {
        val n = prices.size
        val sorted = prices.toSortedSet().toList()
        val m = sorted.size
        val get = { x: Int -> sorted.binarySearch(x) }
        val left = IntArray(n) { -1 }
        val right = IntArray(n) { -1 }
        val bit = IntArray(m + 2) { -1 }
        fun update(i: Int, v: Int) {
            var idx = i + 1
            while (idx < bit.size) {
                bit[idx] = maxOf(bit[idx], v)
                idx += idx and -idx
            }
        }
        fun query(i: Int): Int {
            var res = -1
            var idx = i + 1
            while (idx > 0) {
                res = maxOf(res, bit[idx])
                idx -= idx and -idx
            }
            return res
        }
        for (j in 0 until n) {
            left[j] = query(get(prices[j]) - 1)
            update(get(prices[j]), profits[j])
        }
        bit.fill(-1)
        for (j in n - 1 downTo 0) {
            right[j] = query(m - get(prices[j]) - 2)
            update(m - get(prices[j]) - 1, profits[j])
        }
        var ans = -1
        for (j in 0 until n) {
            if (left[j] != -1 && right[j] != -1) {
                ans = maxOf(ans, left[j] + profits[j] + right[j])
            }
        }
        return ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


class Solution:
    def maxProfit(self, prices: list[int], profits: list[int]) -> int:
        n = len(prices)
        sorted_prices = sorted(set(prices))
        idx = {v: i for i, v in enumerate(sorted_prices)}
        m = len(sorted_prices)
        left = [-1] * n
        right = [-1] * n
        bit = [-1] * (m + 2)
        def update(i: int, v: int):
            i += 1
            while i < len(bit):
                bit[i] = max(bit[i], v)
                i += i & -i
        def query(i: int) -> int:
            res = -1
            i += 1
            while i > 0:
                res = max(res, bit[i])
                i -= i & -i
            return res
        for j in range(n):
            left[j] = query(idx[prices[j]] - 1)
            update(idx[prices[j]], profits[j])
        bit = [-1] * (m + 2)
        for j in range(n - 1, -1, -1):
            right[j] = query(m - idx[prices[j]] - 2)
            update(m - idx[prices[j]] - 1, profits[j])
        ans = -1
        for j in range(n):
            if left[j] != -1 and right[j] != -1:
                ans = max(ans, left[j] + profits[j] + right[j])
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45


impl Solution {
    pub fn max_profit(prices: Vec<i32>, profits: Vec<i32>) -> i32 {
        let n = prices.len();
        let mut sorted = prices.clone();
        sorted.sort();
        sorted.dedup();
        let m = sorted.len();
        let mut left = vec![-1; n];
        let mut right = vec![-1; n];
        let mut bit = vec![-1; m + 2];
        let get = |x: i32| sorted.binary_search(&x).unwrap();
        let mut update = |i: usize, v: i32| {
            let mut idx = i + 1;
            while idx < bit.len() {
                bit[idx] = bit[idx].max(v);
                idx += idx & (!idx + 1);
            }
        };
        let mut query = |i: usize| -> i32 {
            let mut res = -1;
            let mut idx = i + 1;
            while idx > 0 {
                res = res.max(bit[idx]);
                idx -= idx & (!idx + 1);
            }
            res
        };
        for j in 0..n {
            left[j] = query(get(prices[j]) - 1);
            update(get(prices[j]), profits[j]);
        }
        bit = vec![-1; m + 2];
        for j in (0..n).rev() {
            right[j] = query(m - get(prices[j]) - 2);
            update(m - get(prices[j]) - 1, profits[j]);
        }
        let mut ans = -1;
        for j in 0..n {
            if left[j] != -1 && right[j] != -1 {
                ans = ans.max(left[j] + profits[j] + right[j]);
            }
        }
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44


class Solution {
    maxProfit(prices: number[], profits: number[]): number {
        const n = prices.length;
        const sorted = Array.from(new Set(prices)).sort((a, b) => a - b);
        const idx = new Map<number, number>();
        sorted.forEach((v, i) => idx.set(v, i));
        const m = sorted.length;
        const left = Array(n).fill(-1);
        const right = Array(n).fill(-1);
        let bit = Array(m + 2).fill(-1);
        function update(i: number, v: number) {
            i++;
            while (i < bit.length) {
                bit[i] = Math.max(bit[i], v);
                i += i & -i;
            }
        }
        function query(i: number): number {
            let res = -1;
            i++;
            while (i > 0) {
                res = Math.max(res, bit[i]);
                i -= i & -i;
            }
            return res;
        }
        for (let j = 0; j < n; j++) {
            left[j] = query(idx.get(prices[j])! - 1);
            update(idx.get(prices[j])!, profits[j]);
        }
        bit = Array(m + 2).fill(-1);
        for (let j = n - 1; j >= 0; j--) {
            right[j] = query(m - idx.get(prices[j])! - 2);
            update(m - idx.get(prices[j])! - 1, profits[j]);
        }
        let ans = -1;
        for (let j = 0; j < n; j++) {
            if (left[j] !== -1 && right[j] !== -1) {
                ans = Math.max(ans, left[j] + profits[j] + right[j]);
            }
        }
        return ans;
    }
}

Complexity

⏰ Time complexity: O(n log n), where n is the number of items. Each update/query is O(log n) and we do O(n) of them.
🧺 Space complexity: O(n), for the segment tree/BIT and auxiliary arrays.

Problem#

Examples#

Solution#

Method 1 – Efficient DP with Segment Tree or Binary Indexed Tree#

Intuition#

Approach#

Code#

Complexity#