Maximum profitable triplets with increasing prices i

Array Binary Indexed Tree Segment Tree

55.8% acceptance

Mar 31, 2026

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.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn max_profit(prices: Vec<i32>, profits: Vec<i32>) -> i32 {
    let n = prices.len();
    let mut result = -1i32;
    for j in 1..n - 1 {
      let mut max_left = -1i32;
      for i in 0..j {
        if prices[i] < prices[j] {
          max_left = max_left.max(profits[i]);
        }
      }
      if max_left == -1 {
        continue;
      }
      let mut max_right = -1i32;
      for k in j + 1..n {
        if prices[k] > prices[j] {
          max_right = max_right.max(profits[k]);
        }
      }
      if max_right == -1 {
        continue;
      }
      result = result.max(max_left + profits[j] + max_right);
    }
    result
  }
}