Maximum profitable triplets with increasing prices ii

Array Binary Indexed Tree Segment Tree

46.1% 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(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_profit(prices: Vec<i32>, profits: Vec<i32>) -> i32 {
    let n = prices.len();
    let max_p = 5000usize;

    struct BIT {
      tree: Vec<i32>,
    }
    impl BIT {
      fn new(n: usize) -> Self {
        BIT { tree: vec![0; n + 1] }
      }
      fn update(&mut self, mut i: usize, val: i32) {
        while i < self.tree.len() {
          self.tree[i] = self.tree[i].max(val);
          i += i & i.wrapping_neg();
        }
      }
      fn query(&self, mut i: usize) -> i32 {
        let mut res = 0;
        while i > 0 {
          res = res.max(self.tree[i]);
          i -= i & i.wrapping_neg();
        }
        res
      }
    }

    let mut max_left = vec![0i32; n];
    let mut left_bit = BIT::new(max_p);
    for j in 0..n {
      if prices[j] > 1 {
        max_left[j] = left_bit.query((prices[j] - 1) as usize);
      }
      left_bit.update(prices[j] as usize, profits[j]);
    }

    let mut max_right = vec![0i32; n];
    let mut right_bit = BIT::new(max_p);
    for j in (0..n).rev() {
      let q = max_p as i32 - prices[j];
      if q > 0 {
        max_right[j] = right_bit.query(q as usize);
      }
      right_bit.update((max_p as i32 - prices[j] + 1) as usize, profits[j]);
    }

    let mut result = -1i32;
    for j in 0..n {
      if max_left[j] > 0 && max_right[j] > 0 {
        result = result.max(max_left[j] + profits[j] + max_right[j]);
      }
    }
    result
  }
}