Maximum increasing triplet value

use std::collections::BTreeSet;

impl Solution {
  pub fn maximum_triplet_value(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    // For triplet (i, j, k) with i < j < k and nums[i] < nums[j] < nums[k],
    // maximize nums[i] - nums[j] + nums[k].
    // = (nums[k] - nums[j]) + nums[i]
    // Since nums[i] < nums[j] < nums[k], we want:
    //   - nums[k] as large as possible
    //   - nums[j] as small as possible (but > nums[i])
    //   - nums[i] as large as possible (but < nums[j])
    //
    // For each j, we need max nums[i] where i < j and nums[i] < nums[j],
    // and max nums[k] where k > j and nums[k] > nums[j].
    
    // suffix_max[j] = max nums[k] for k > j where nums[k] > nums[j]
    // We can compute: suffix_max_val[j] = max of nums[j+1..n]
    // If suffix_max_val[j] > nums[j], that's the best k value.
    
    let mut suffix_max = vec![0i32; n];
    suffix_max[n - 1] = nums[n - 1];
    for i in (0..n - 1).rev() {
      suffix_max[i] = suffix_max[i + 1].max(nums[i]);
    }
    
    // For each j (middle element), we need:
    // - The largest nums[i] < nums[j] from the left
    // - The largest nums[k] > nums[j] from the right (suffix_max[j+1] if > nums[j])
    // Use a BTreeSet to track elements seen so far on the left
    
    let mut left_set = BTreeSet::new();
    let mut ans = i32::MIN;
    
    for j in 1..n - 1 {
      left_set.insert(nums[j - 1]);
      
      // Best k value: suffix_max[j+1], must be > nums[j]
      let best_k = suffix_max[j + 1];
      if best_k <= nums[j] {
        continue;
      }
      
      // Best i value: largest element in left_set that is < nums[j]
      if let Some(&best_i) = left_set.range(..nums[j]).next_back() {
        let val = best_i - nums[j] + best_k;
        ans = ans.max(val);
      }
    }
    
    ans
  }
}