Find maximum value in a constrained sequence

Array Greedy

62.1% acceptance

Mar 15, 2026

You are given an integer n, a 2D integer array restrictions, and an integer array diff of length n - 1. Construct a sequence a[0..n-1] where a[0]=0, all elements non-negative, |a[i] - a[i+1]| <= diff[i], and a[idx] <= maxVal for each restriction. Maximize the largest value in the sequence.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn find_max_val(n: i32, restrictions: Vec<Vec<i32>>, diff: Vec<i32>) -> i32 {
    let n = n as usize;
    // upper[i] = max possible value at position i
    let mut upper = vec![i64::MAX; n];
    upper[0] = 0;
    for r in &restrictions {
      let idx = r[0] as usize;
      let max_val = r[1] as i64;
      upper[idx] = upper[idx].min(max_val);
    }
    // Forward pass: propagate from left to right
    // a[i+1] <= a[i] + diff[i], so upper[i+1] <= upper[i] + diff[i]
    for i in 0..n - 1 {
      let next = upper[i].saturating_add(diff[i] as i64);
      upper[i + 1] = upper[i + 1].min(next);
    }
    // Backward pass: propagate from right to left
    // a[i] <= a[i+1] + diff[i], so upper[i] <= upper[i+1] + diff[i]
    for i in (0..n - 1).rev() {
      let prev = upper[i + 1].saturating_add(diff[i] as i64);
      upper[i] = upper[i].min(prev);
    }
    *upper.iter().max().unwrap() as i32
  }
}