2907

2907. Maximum Profitable Triplets With Increasing Prices I (Medium)

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 the maximum profit we can get, and -1 if it's not possible to pick three items with the given condition.

 

Example 1:

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:

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:

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] <= 106
• 1 <= profits[i] <= 106

Companies: IBM

Related Topics:
Array, Dynamic Programming

Hints:

• Let's fix the middle chosen item.
• For a fixed item with an index j, iterate over items with an index k > j such that prices[k] > prices[j].
• Find the maximum profit[k] with the above condition. Let's call this maximum value max_right.
• Do the same for items with an index i < j such that prices[i] < prices[j] and find the maximum profit[i] among them. Let's call this maximum value max_left.
• Now the profit when an item with the index j is the middle one would be profit[j] + max_right + max_left.
• Finally, do the above procedure for all j's and find the maximum profit among them. That would be the final answer.

Solution 1.

// OJ: https://leetcode.com/problems/maximum-profitable-triplets-with-increasing-prices-i
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
    int maxProfit(vector<int>& A, vector<int>& B) {
        int N = A.size(), ans = -1;
        for (int i = 1; i < N - 1; ++i) {
            int left = 0, right = 0;
            for (int j = 0; j < N; ++j) {
                if (j < i) {
                    if (A[j] < A[i]) left = max(left, B[j]);
                } else if (j > i) {
                    if (A[j] > A[i]) right = max(right, B[j]);
                }
            }
            if (left && right) ans = max(ans, left + right + B[i]);
        }
        return ans;
    }
};

Solution 2. Monotonic Map

// OJ: https://leetcode.com/problems/maximum-profitable-triplets-with-increasing-prices-i
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(N)
// Ref: https://leetcode.com/problems/maximum-profitable-triplets-with-increasing-prices-i/solutions/4183514/just-binary-search-map-lower-bound-upper-bound/
class Solution {
    void insert(map<int, int> &m, int price, int profit) { // this method ensures that both of the prices and profits are monotinic increasing.
        auto it = m.upper_bound(price);
        if (it != m.begin() && prev(it)->second >= profit) return; // If there was already an item with no greater price and no less profit, no need to insert.
        for (it = m.lower_bound(price); it != m.end() && it->second <= profit; m.erase(it++)); // If there was already an item with no less price and no greater profit, this item can be deleted.
        m[price] = profit;
    }
public:
    int maxProfit(vector<int>& A, vector<int>& B) {
        int N = A.size(), ans = -1;
        map<int, int> one, two; // `one`/`two` is a monotonic map corresponding to the maximum profit we can get from a subsequent of length one/two. The key is the price of the last element in the subsequence, and the value is the total profit of the subsequence. Both the keys and values are monotonic increasing.
        for (int i = 0; i < N; ++i) {
            auto it = two.lower_bound(A[i]);
            if (it != two.begin()) ans = max(ans, prev(it)->second + B[i]);
            it = one.lower_bound(A[i]);
            if (it != one.begin()) insert(two, A[i], prev(it)->second + B[i]);
            insert(one, A[i], B[i]);
        }
        return ans;
    }
};