2907. Maximum Profitable Triplets With Increasing Prices I

Description

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

Solutions

• class Solution {
public int maxProfit(int[] prices, int[] profits) {
int n = prices.length;
int ans = -1;
for (int j = 0; j < n; ++j) {
int left = 0, right = 0;
for (int i = 0; i < j; ++i) {
if (prices[i] < prices[j]) {
left = Math.max(left, profits[i]);
}
}
for (int k = j + 1; k < n; ++k) {
if (prices[j] < prices[k]) {
right = Math.max(right, profits[k]);
}
}
if (left > 0 && right > 0) {
ans = Math.max(ans, left + profits[j] + right);
}
}
return ans;
}
}

• class Solution {
public:
int maxProfit(vector<int>& prices, vector<int>& profits) {
int n = prices.size();
int ans = -1;
for (int j = 0; j < n; ++j) {
int left = 0, right = 0;
for (int i = 0; i < j; ++i) {
if (prices[i] < prices[j]) {
left = max(left, profits[i]);
}
}
for (int k = j + 1; k < n; ++k) {
if (prices[j] < prices[k]) {
right = max(right, profits[k]);
}
}
if (left && right) {
ans = max(ans, left + profits[j] + right);
}
}
return ans;
}
};

• class Solution:
def maxProfit(self, prices: List[int], profits: List[int]) -> int:
n = len(prices)
ans = -1
for j, x in enumerate(profits):
left = right = 0
for i in range(j):
if prices[i] < prices[j] and left < profits[i]:
left = profits[i]
for k in range(j + 1, n):
if prices[j] < prices[k] and right < profits[k]:
right = profits[k]
if left and right:
ans = max(ans, left + x + right)
return ans


• func maxProfit(prices []int, profits []int) int {
n := len(prices)
ans := -1
for j, x := range profits {
left, right := 0, 0
for i := 0; i < j; i++ {
if prices[i] < prices[j] {
left = max(left, profits[i])
}
}
for k := j + 1; k < n; k++ {
if prices[j] < prices[k] {
right = max(right, profits[k])
}
}
if left > 0 && right > 0 {
ans = max(ans, left+x+right)
}
}
return ans
}

func max(a, b int) int {
if a > b {
return a
}
return b
}

• function maxProfit(prices: number[], profits: number[]): number {
const n = prices.length;
let ans = -1;
for (let j = 0; j < n; ++j) {
let [left, right] = [0, 0];
for (let i = 0; i < j; ++i) {
if (prices[i] < prices[j]) {
left = Math.max(left, profits[i]);
}
}
for (let k = j + 1; k < n; ++k) {
if (prices[j] < prices[k]) {
right = Math.max(right, profits[k]);
}
}
if (left > 0 && right > 0) {
ans = Math.max(ans, left + profits[j] + right);
}
}
return ans;
}


• impl Solution {
pub fn max_profit(prices: Vec<i32>, profits: Vec<i32>) -> i32 {
let n = prices.len();
let mut ans = -1;

for j in 0..n {
let mut left = 0;
let mut right = 0;

for i in 0..j {
if prices[i] < prices[j] {
left = left.max(profits[i]);
}
}

for k in (j + 1)..n {
if prices[j] < prices[k] {
right = right.max(profits[k]);
}
}

if left > 0 && right > 0 {
ans = ans.max(left + profits[j] + right);
}
}

ans
}
}