Reverse subarray to maximize array value

Array Math Greedy

43.8% acceptance

Feb 25, 2026

493

You are given an integer array nums. The value of this array is defined as the sum of |nums[i] - nums[i + 1]| for all 0 <= i < nums.length - 1. You are allowed to select any subarray of the given array and reverse it. You can perform this operation only once. Find maximum possible value of the final array.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn max_value_after_reverse(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    let original: i32 = (0..n - 1).map(|i| (nums[i] - nums[i + 1]).abs()).sum();
    let mut best_gain = 0i32;

    // Case 1: both boundaries exist
    // gain = 2 * max(0, max_min - min_max)
    let mut max_min = i32::MIN;
    let mut min_max = i32::MAX;
    for i in 0..n - 1 {
      max_min = max_min.max(nums[i].min(nums[i + 1]));
      min_max = min_max.min(nums[i].max(nums[i + 1]));
    }
    if max_min > min_max {
      best_gain = best_gain.max(2 * (max_min - min_max));
    }

    // Case 2: left boundary only (l=0, vary r): gain = |a[0]-a[r+1]| - |a[r]-a[r+1]|
    for j in 1..n {
      let gain = (nums[0] - nums[j]).abs() - (nums[j - 1] - nums[j]).abs();
      best_gain = best_gain.max(gain);
    }

    // Case 3: right boundary only (r=n-1, vary l): gain = |a[l-1]-a[n-1]| - |a[l-1]-a[l]|
    for i in 0..n - 1 {
      let gain = (nums[i] - nums[n - 1]).abs() - (nums[i] - nums[i + 1]).abs();
      best_gain = best_gain.max(gain);
    }

    original + best_gain
  }
}