Trionic array ii

impl Solution {
  pub fn max_sum_trionic(nums: Vec<i32>) -> i64 {
    let n = nums.len();

    // prefix[i] = sum of nums[0..i]
    let mut prefix = vec![0i64; n + 1];
    for i in 0..n {
      prefix[i + 1] = prefix[i] + nums[i] as i64;
    }

    // For trionic subarray l..=r with peak p and trough q (l < p < q < r):
    //   nums[l..=p] strictly increasing, nums[p..=q] strictly decreasing, nums[q..=r] strictly increasing
    //   total sum = prefix[r+1] - prefix[l]
    //
    // Key insight: maximise prefix[r+1] - prefix[l] over all valid (p,q).
    //   - l can be any index in [left_ext[p], p-1]  → minimise prefix[l]
    //   - r can be any index in [q+1, right_ext[q]] → maximise prefix[r+1]
    //
    // Precompute O(n):
    //   min_left_val[p] = min(prefix[l]) for l in [left_ext[p], p-1]
    //     (i64::MAX when no valid l, i.e. nums[p-1] >= nums[p])
    //   max_right_val[q] = max(prefix[r+1]) for r in [q+1, right_ext[q]]
    //     (i64::MIN when no valid r, i.e. nums[q] >= nums[q+1])
    //
    // Then sweep each maximal strictly-decreasing run p_start..=q_end:
    //   For any split p < q in the run: candidate = max_right_val[q] - min_left_val[p].
    //   Track running min of min_left_val[p] as p advances, evaluate each q.

    // --- min_left_val ---
    let mut min_left_val = vec![i64::MAX; n];
    for p in 1..n {
      if nums[p - 1] < nums[p] {
        if p >= 2 && nums[p - 2] < nums[p - 1] {
          // Same left-increasing run as p-1; inherit and consider prefix[p-1]
          min_left_val[p] = min_left_val[p - 1].min(prefix[p - 1]);
        } else {
          // Run starts at p-1, only valid l = p-1
          min_left_val[p] = prefix[p - 1];
        }
      }
    }

    // --- max_right_val ---
    let mut max_right_val = vec![i64::MIN; n];
    for q in (0..n - 1).rev() {
      if nums[q] < nums[q + 1] {
        if q + 2 < n && nums[q + 1] < nums[q + 2] {
          // Same right-increasing run as q+1; inherit and consider prefix[q+2]
          max_right_val[q] = max_right_val[q + 1].max(prefix[q + 2]);
        } else {
          // Run ends at q+1, only valid r = q+1
          max_right_val[q] = prefix[q + 2];
        }
      }
    }

    let mut best = i64::MIN;

    // Enumerate every maximal strictly-decreasing run and find the best (p, q) split.
    let mut i = 0;
    while i < n - 1 {
      if nums[i] > nums[i + 1] {
        let p_start = i;
        // Extend to the end of the decreasing run
        while i < n - 1 && nums[i] > nums[i + 1] {
          i += 1;
        }
        let q_end = i; // nums[p_start] > … > nums[q_end]

        // Sweep: track running min of min_left_val[pos] as pos (=p) advances,
        // and for each subsequent pos+1 (=q) evaluate the candidate sum.
        let mut running_min_left = i64::MAX;
        for pos in p_start..=q_end {
          // Use pos as p: update running minimum of left-prefix
          if min_left_val[pos] < i64::MAX {
            running_min_left = running_min_left.min(min_left_val[pos]);
          }
          // Use pos+1 as q (strictly after p)
          let q_pos = pos + 1;
          if q_pos <= q_end
            && max_right_val[q_pos] > i64::MIN
            && running_min_left < i64::MAX
          {
            best = best.max(max_right_val[q_pos] - running_min_left);
          }
        }
      } else {
        i += 1;
      }
    }

    best
  }
}