Skip to main content
Back to problems
#3891
Medium Algorithms

Minimum increase to maximize special indices

Array Dynamic Programming Greedy Prefix Sum
19.5% acceptance
May 13, 2026
100
11
You are given an integer array nums of length n. An index i (0 < i < n - 1) is special if nums[i] > nums[i - 1] and nums[i] > nums[i + 1]. You may perform operations where you choose any index i and increase nums[i] by 1. Your goal is to: Maximize the number of special indices. Minimize the total number of operations required to achieve that maximum. Return an integer denoting the minimum total number of operations required.

Solution

Rust
Time O(n)
Space O(1)
LeetCode
solution.rs 
impl Solution {
  pub fn min_increase(nums: Vec<i32>) -> i64 {
    let n = nums.len();
    if n < 3 { return 0; }
    let cost = |i: usize| -> i64 {
      let mx = nums[i - 1].max(nums[i + 1]) as i64;
      (mx + 1 - nums[i] as i64).max(0)
    };
    let better = |a: (i64, i64), b: (i64, i64)| -> (i64, i64) {
      if a.0 > b.0 { a }
      else if b.0 > a.0 { b }
      else if a.1 <= b.1 { a }
      else { b }
    };
    let mut nt = (0i64, 0i64);
    let mut t = (i64::MIN / 2, 0i64);
    for i in 1..=n - 2 {
      let c = cost(i);
      let new_nt = better(nt, t);
      let new_t = (nt.0 + 1, nt.1 + c);
      nt = new_nt;
      t = new_t;
    }
    better(nt, t).1
  }
}