Problem Description

Given an integer array nums, define the array value as the sum of |nums[i] - nums[i+1]| for all valid indices i (where 0 ≤ i < n-1). Your task is to maximize this array value by reversing exactly one subarray (i.e., you choose a contiguous segment and reverse it in place).

You need to return the maximum possible array value after making at most one such reversal. If you choose not to reverse any subarray, the original array value applies.

Constraints:

• 2 ≤ nums.length ≤ 10^5
• -10^5 ≤ nums[i] ≤ 10^5

Thought Process

The naive approach would be to try reversing every possible subarray and compute the resulting array value, but with O(n^2) possible subarrays, this is too slow for large arrays.

Instead, we need to analyze how reversing a subarray affects the array value. Reversing a segment only changes the values at the boundaries of the reversed subarray, so we should focus on how these boundaries change the sum of absolute differences. The goal is to find the subarray whose reversal gives the largest increase in array value.

The key insight is that most of the array remains unchanged after a reversal, except for the pairs that straddle the edges of the reversed segment. If we can efficiently compute the best possible gain from any reversal, we can solve the problem in linear time.

Solution Approach

We'll break down the solution into clear steps:

1. Compute the initial array value: Calculate the sum of |nums[i] - nums[i+1]| for all i.
2. Understand the effect of a reversal: Reversing a subarray from l to r only affects the pairs at the edges: (nums[l-1], nums[l]) and (nums[r], nums[r+1]) (if they exist). All other differences remain the same or are just rearranged within the subarray.
3. Calculate the potential gain: For each possible reversal, determine how much the sum changes.
   • For the edge pairs, after reversal, the differences become |nums[l-1] - nums[r]| and |nums[l] - nums[r+1]|.
   • The potential gain is the difference between the new and old edge differences.
4. Optimize for all possible reversals:
   • To maximize the gain, check all possible values for l and r at the boundaries (i.e., reversing from the start or to the end).
   • For reversals not at the boundaries, track the minimum and maximum of max(min(nums[i], nums[i+1])) and min(max(nums[i], nums[i+1])) to find the best possible gain.
5. Return the maximum possible array value: Add the best gain to the initial array value.

This approach ensures we only traverse the array a few times, achieving O(n) time complexity.

Example Walkthrough

Let's consider the example nums = [2, 3, 1, 5, 4].

• Initial array value:
  • |2-3| = 1
  • |3-1| = 2
  • |1-5| = 4
  • |5-4| = 1
  • Total = 1 + 2 + 4 + 1 = 8
• Check reversal at the start (reverse [0, r]):
  • For r=1: Reverse [2,3] → [3,2], only the first two elements change, but the overall value remains the same.
  • For r=2: Reverse [2,3,1] → [1,3,2]. The edge pairs are (none) and (1,5). The difference at the edge goes from |1-5|=4 to |2-5|=3. The total decreases.
• Check reversal at the end (reverse [l, n-1]):
  • For l=3: Reverse [5,4] → [4,5], only the last two elements change, but the total remains the same.
• Check all possible subarrays for maximal gain:
  • By tracking the min of max(nums[i], nums[i+1]) and max of min(nums[i], nums[i+1]), we can compute the best improvement possible.
• Result: The best reversal yields a maximal array value, which the algorithm computes efficiently.

Time and Space Complexity

Brute-force approach: Trying all possible subarrays to reverse would require O(n^2) time, as each reversal takes O(n) and there are O(n^2) possible subarrays.

Optimized approach: By focusing on the effect of reversing on the boundary pairs, we can compute the maximal gain in O(n) time and O(1) extra space, aside from the input and some variables for tracking min/max values.

Summary

The key insight is that reversing a subarray only affects the edges of the reversed segment. By efficiently computing the potential gain for all possible reversals, we can solve the problem in linear time. This approach avoids brute-force and leverages mathematical reasoning to optimize the solution. The elegance lies in reducing a seemingly complex problem to simple boundary analysis.

Code Implementation

class Solution:
    def maxValueAfterReverse(self, nums):
        n = len(nums)
        total = 0
        min_max = float('inf')
        max_min = float('-inf')
        for i in range(n - 1):
            a, b = nums[i], nums[i + 1]
            total += abs(a - b)
            min_max = min(min_max, max(a, b))
            max_min = max(max_min, min(a, b))
        gain = 0
        # Try reversing from the start to i
        for i in range(1, n - 1):
            gain = max(gain, abs(nums[0] - nums[i + 1]) - abs(nums[i] - nums[i + 1]))
        # Try reversing from i to end
        for i in range(n - 1):
            gain = max(gain, abs(nums[-1] - nums[i]) - abs(nums[i] - nums[i + 1]))
        # Try reversing in the middle
        gain = max(gain, 2 * (max_min - min_max))
        return total + gain
      

class Solution {
public:
    int maxValueAfterReverse(vector<int>& nums) {
        int n = nums.size();
        int total = 0;
        int min_max = INT_MAX, max_min = INT_MIN;
        for (int i = 0; i < n - 1; ++i) {
            int a = nums[i], b = nums[i + 1];
            total += abs(a - b);
            min_max = min(min_max, max(a, b));
            max_min = max(max_min, min(a, b));
        }
        int gain = 0;
        for (int i = 1; i < n - 1; ++i) {
            gain = max(gain, abs(nums[0] - nums[i + 1]) - abs(nums[i] - nums[i + 1]));
        }
        for (int i = 0; i < n - 1; ++i) {
            gain = max(gain, abs(nums[n - 1] - nums[i]) - abs(nums[i] - nums[i + 1]));
        }
        gain = max(gain, 2 * (max_min - min_max));
        return total + gain;
    }
};
      

class Solution {
    public int maxValueAfterReverse(int[] nums) {
        int n = nums.length;
        int total = 0;
        int minMax = Integer.MAX_VALUE, maxMin = Integer.MIN_VALUE;
        for (int i = 0; i < n - 1; ++i) {
            int a = nums[i], b = nums[i + 1];
            total += Math.abs(a - b);
            minMax = Math.min(minMax, Math.max(a, b));
            maxMin = Math.max(maxMin, Math.min(a, b));
        }
        int gain = 0;
        for (int i = 1; i < n - 1; ++i) {
            gain = Math.max(gain, Math.abs(nums[0] - nums[i + 1]) - Math.abs(nums[i] - nums[i + 1]));
        }
        for (int i = 0; i < n - 1; ++i) {
            gain = Math.max(gain, Math.abs(nums[n - 1] - nums[i]) - Math.abs(nums[i] - nums[i + 1]));
        }
        gain = Math.max(gain, 2 * (maxMin - minMax));
        return total + gain;
    }
}
      

var maxValueAfterReverse = function(nums) {
    const n = nums.length;
    let total = 0;
    let minMax = Infinity, maxMin = -Infinity;
    for (let i = 0; i < n - 1; ++i) {
        let a = nums[i], b = nums[i + 1];
        total += Math.abs(a - b);
        minMax = Math.min(minMax, Math.max(a, b));
        maxMin = Math.max(maxMin, Math.min(a, b));
    }
    let gain = 0;
    for (let i = 1; i < n - 1; ++i) {
        gain = Math.max(gain, Math.abs(nums[0] - nums[i + 1]) - Math.abs(nums[i] - nums[i + 1]));
    }
    for (let i = 0; i < n - 1; ++i) {
        gain = Math.max(gain, Math.abs(nums[n - 1] - nums[i]) - Math.abs(nums[i] - nums[i + 1]));
    }
    gain = Math.max(gain, 2 * (maxMin - minMax));
    return total + gain;
};