# Reverse Subarray To Maximize Array Value
**Difficulty:** HARD
[External](https://leetcode.com/problems/reverse-subarray-to-maximize-array-value)
Canonical: https://scaleengineer.com/dsa/problems/reverse-subarray-to-maximize-array-value
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
---
## Problem
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.

**Example 1:**

**Input:** nums = [2,3,1,5,4]
**Output:** 10
**Explanation:** By reversing the subarray [3,1,5] the array becomes [2,5,1,3,4] whose value is 10.

**Example 2:**

**Input:** nums = [2,4,9,24,2,1,10]
**Output:** 68

**Constraints:**

* `2 <= nums.length <= 3 * 104`
* `-105 <= nums[i] <= 105`
* The answer is guaranteed to fit in a 32-bit integer.

# Approaches
## Brute Force Simulation
The most straightforward approach is to simulate the process directly. We can try reversing every possible subarray, calculate the resulting array's value, and keep track of the maximum value seen. This involves three nested loops: two to define the subarray's start and end points, and a third to calculate the value of the array after the reversal.
**Time:** O(N³), where N is the number of elements in the array. There are O(N²) possible subarrays. For each, copying the array takes O(N), reversing takes O(j-i) which is O(N), and calculating the new value takes O(N). This leads to an overall complexity of O(N² * N) = O(N³). · **Space:** O(N), where N is the number of elements in the array. This is for storing the temporary copy of the array in each iteration.
**Pros:** Simple to understand and implement.
**Cons:** Extremely inefficient due to its cubic time complexity.; Not feasible for the given constraints on the input size (`n` up to 3 * 10^4).
### Explanation
This brute-force method iterates through all possible start (`i`) and end (`j`) indices of a subarray. For each subarray `nums[i...j]`, it creates a copy of the original array, performs the reversal on the copy, and then computes the value of the new array from scratch. The value is the sum of absolute differences of adjacent elements. The maximum value found across all possible reversals is the answer.

```java
class Solution {
    public int maxValueAfterReverse(int[] nums) {
        int n = nums.length;
        int maxVal = 0;

        // Calculate initial value to handle the case of no reversal (or reversing a single element)
        for (int i = 0; i < n - 1; i++) {
            maxVal += Math.abs(nums[i] - nums[i + 1]);
        }

        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                // Create a temporary array and reverse the subarray [i, j]
                int[] temp = new int[n];
                System.arraycopy(nums, 0, temp, 0, n);
                reverse(temp, i, j);

                // Calculate the value of the new array
                int currentVal = 0;
                for (int k = 0; k < n - 1; k++) {
                    currentVal += Math.abs(temp[k] - temp[k + 1]);
                }
                maxVal = Math.max(maxVal, currentVal);
            }
        }
        return maxVal;
    }

    private void reverse(int[] arr, int start, int end) {
        while (start < end) {
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
            start++;
            end--;
        }
    }
}
```
### Algorithm
1. Initialize `maxValue` to 0.
2. Generate every possible subarray `nums[i...j]` by iterating `i` from `0` to `n-1` and `j` from `i` to `n-1`.
3. For each subarray:
    a. Create a temporary copy of the `nums` array.
    b. Reverse the subarray from index `i` to `j` in the temporary array.
    c. Calculate the 'value' of this modified temporary array by summing the absolute differences of adjacent elements: `sum(|temp[k] - temp[k+1]|)`.
    d. Update `maxValue = max(maxValue, calculated_value)`.
4. Return `maxValue`.

## Optimized Brute Force by Calculating Gain
We can improve upon the brute-force approach by observing that when we reverse a subarray `nums[i...j]`, the sum of absolute differences for elements outside this subarray and for elements completely inside this subarray remains unchanged. The only change in the total value comes from the connections at the boundaries of the subarray. This allows us to calculate the change in value in O(1) time for each subarray, reducing the overall complexity.
**Time:** O(N²), where N is the number of elements. We have two nested loops to iterate through all O(N²) subarrays, and the calculation for each is O(1). · **Space:** O(1), as we are not using any extra space that scales with the input size.
**Pros:** Significantly faster than the O(N³) approach.; Avoids creating new arrays in memory for each subarray.
**Cons:** Still too slow for the given constraints, as O(N²) is not efficient enough.
### Explanation
First, we compute the initial value of the array. Then, we iterate through all possible subarrays `nums[i...j]`. Instead of creating a new array and recalculating the entire sum, we calculate the 'gain' directly. 

When a subarray `nums[i...j]` is reversed, the pairs of adjacent elements that change are at the boundaries. The original boundary pairs are `(nums[i-1], nums[i])` and `(nums[j], nums[j+1])`. After reversal, they become `(nums[i-1], nums[j])` and `(nums[i], nums[j+1])`. The change in value is the difference in the sum of absolute differences of these pairs. We calculate this gain for every subarray and find the maximum possible gain. Special care is needed for subarrays that start at index 0 or end at index `n-1`.

```java
class Solution {
    public int maxValueAfterReverse(int[] nums) {
        int n = nums.length;
        int baseValue = 0;
        for (int i = 0; i < n - 1; i++) {
            baseValue += Math.abs(nums[i] - nums[i + 1]);
        }

        int maxGain = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int currentGain = 0;
                if (i > 0 && j < n - 1) { // Internal subarray
                    int originalBoundarySum = Math.abs(nums[i - 1] - nums[i]) + Math.abs(nums[j] - nums[j + 1]);
                    int newBoundarySum = Math.abs(nums[i - 1] - nums[j]) + Math.abs(nums[i] - nums[j + 1]);
                    currentGain = newBoundarySum - originalBoundarySum;
                } else if (i == 0 && j < n - 1) { // Subarray starts at the beginning
                    int originalBoundarySum = Math.abs(nums[j] - nums[j + 1]);
                    int newBoundarySum = Math.abs(nums[0] - nums[j + 1]);
                    currentGain = newBoundarySum - originalBoundarySum;
                } else if (i > 0 && j == n - 1) { // Subarray ends at the end
                    int originalBoundarySum = Math.abs(nums[i - 1] - nums[i]);
                    int newBoundarySum = Math.abs(nums[i - 1] - nums[n - 1]);
                    currentGain = newBoundarySum - originalBoundarySum;
                } // If i=0 and j=n-1, gain is 0.
                maxGain = Math.max(maxGain, currentGain);
            }
        }

        return baseValue + maxGain;
    }
}
```
### Algorithm
1. Calculate the initial value of the array, `baseValue = sum(|nums[i] - nums[i+1]|)`.
2. Initialize `maxGain = 0`.
3. Iterate through all possible start indices `i` from `0` to `n-1`.
4. For each `i`, iterate through all possible end indices `j` from `i` to `n-1`.
5. For each pair `(i, j)`, calculate the change in value (`gain`) that would result from reversing `nums[i...j]`. This can be done in O(1) by only considering the boundaries of the subarray.
   - If the subarray is internal (`0 < i <= j < n-1`), the gain is `|nums[i-1] - nums[j]| + |nums[i] - nums[j+1]| - |nums[i-1] - nums[i]| - |nums[j] - nums[j+1]|`.
   - Handle edge cases where the subarray touches the array's start or end.
6. Update `maxGain = max(maxGain, gain)`.
7. The final answer is `baseValue + maxGain`.

## Linear Time Solution with Mathematical Insight
A linear time solution can be achieved by analyzing the formula for the gain in value. The problem can be broken down into three cases for the reversed subarray: it touches the left end, it touches the right end, or it's in the middle. The first two cases can be solved with simple linear scans. The third, most complex case, can also be optimized to a linear scan through a mathematical insight.
**Time:** O(N), where N is the number of elements. The algorithm consists of a few separate linear passes over the array. · **Space:** O(1), as it only uses a few variables to store state.
**Pros:** Highly efficient with linear time complexity.; Optimal solution for the given problem constraints.
**Cons:** The logic is complex and relies on a non-obvious mathematical insight about the gain formula.
### Explanation
The core idea is to find the maximum possible `gain` over the `baseValue` and add it. The gain depends on where the reversed subarray `[i, j]` is located.

1.  **Initial Value**: First, calculate the `baseValue = sum(|nums[k] - nums[k+1]|)` for `k` from `0` to `n-2`.

2.  **Reversal at Endpoints**: 
    *   If we reverse `[0...j]`, the value changes by `|nums[0] - nums[j+1]| - |nums[j] - nums[j+1]|`. We can iterate through all `j` to find the max gain for this case.
    *   If we reverse `[i...n-1]`, the value changes by `|nums[i-1] - nums[n-1]| - |nums[i-1] - nums[i]|`. We can iterate through all `i` to find the max gain for this case.

3.  **Internal Reversal**: For a subarray `[i...j]` where `0 < i <= j < n-1`, the gain is `|nums[i-1] - nums[j]| + |nums[i] - nums[j+1]| - |nums[i-1] - nums[i]| - |nums[j] - nums[j+1]|`. A key insight is that this expression is maximized when the two original boundary pairs `(nums[i-1], nums[i])` and `(nums[j], nums[j+1])` represent value ranges that are far apart. Let `u_k = max(nums[k], nums[k+1])` and `v_k = min(nums[k], nums[k+1])`. The gain is maximized by `2 * (max(v) - min(u))`, where `max(v)` is the maximum of all `v_k`'s and `min(u)` is the minimum of all `u_k`'s. We can find this in a single pass.

By combining the maximum gain from all three cases, we can find the overall `maxGain` in O(N) time.

```java
class Solution {
    public int maxValueAfterReverse(int[] nums) {
        int n = nums.length;
        long baseValue = 0;
        for (int i = 0; i < n - 1; i++) {
            baseValue += Math.abs(nums[i] - nums[i + 1]);
        }

        int maxGain = 0;

        // Case 1: Reversing a subarray that includes an endpoint.
        // This is equivalent to changing one pair (a, b) to (a, c)
        // where a is an endpoint.
        for (int i = 1; i < n; i++) {
            // Reverse [0...i-1]. Change is at boundary i-1, i.
            // Original: |nums[i-1] - nums[i]|. New: |nums[0] - nums[i]|.
            maxGain = Math.max(maxGain, Math.abs(nums[i] - nums[0]) - Math.abs(nums[i] - nums[i-1]));
        }
        for (int i = 0; i < n - 1; i++) {
            // Reverse [i+1...n-1]. Change is at boundary i, i+1.
            // Original: |nums[i] - nums[i+1]|. New: |nums[i] - nums[n-1]|.
            maxGain = Math.max(maxGain, Math.abs(nums[i] - nums[n-1]) - Math.abs(nums[i] - nums[i+1]));
        }

        // Case 2: Reversing an internal subarray [i...j].
        // Gain = |nums[i-1]-nums[j]| + |nums[i]-nums[j+1]| - |nums[i-1]-nums[i]| - |nums[j]-nums[j+1]|
        // This is maximized by 2 * (max(min_pair) - min(max_pair))
        int min_u = Integer.MAX_VALUE;
        int max_v = Integer.MIN_VALUE;

        for (int i = 0; i < n - 1; i++) {
            int u = Math.max(nums[i], nums[i + 1]);
            int v = Math.min(nums[i], nums[i + 1]);
            min_u = Math.min(min_u, u);
            max_v = Math.max(max_v, v);
        }
        
        int internalGain = 2 * (max_v - min_u);
        maxGain = Math.max(maxGain, internalGain);

        return (int) (baseValue + maxGain);
    }
}
```
### Algorithm
1. Calculate the initial `baseValue` of the array.
2. Initialize `maxGain = 0`.
3. **Handle reversals touching an endpoint:**
   a. Iterate `i` from `1` to `n-1`. The gain from reversing `[0...i-1]` is `|nums[i] - nums[0]| - |nums[i] - nums[i-1]|`. Update `maxGain`.
   b. Iterate `i` from `0` to `n-2`. The gain from reversing `[i+1...n-1]` is `|nums[i] - nums[n-1]| - |nums[i] - nums[i+1]|`. Update `maxGain`.
4. **Handle internal reversals `[i...j]`:**
   a. The gain is `|nums[i-1]-nums[j]| + |nums[i]-nums[j+1]| - |nums[i-1]-nums[i]| - |nums[j]-nums[j+1]|`.
   b. This gain is maximized when the intervals `[min(nums[k], nums[k+1]), max(nums[k], nums[k+1])]` and `[min(nums[l], nums[l+1]), max(nums[l], nums[l+1])]` are disjoint and far apart, where `k=i-1` and `l=j`.
   c. The maximum gain from this case is `2 * max(max_v - min_u, 0)`, where `max_v` is the maximum of all `min(nums[k], nums[k+1])` and `min_u` is the minimum of all `max(nums[k], nums[k+1])`.
   d. We can find this maximum gain in a single pass. Initialize `max_v = -infinity` and `min_u = +infinity`. Iterate `k` from `0` to `n-2`, updating `max_v` and `min_u` and the potential gain at each step.
5. Update `maxGain` with the gain from the internal reversal case.
6. The final answer is `baseValue + maxGain`.

# Solutions
### Java

```java
class Solution {
public
  int maxValueAfterReverse(int[] nums) {
    int n = nums.length;
    int s = 0;
    for (int i = 0; i < n - 1; ++i) {
      s += Math.abs(nums[i] - nums[i + 1]);
    }
    int ans = s;
    for (int i = 0; i < n - 1; ++i) {
      ans = Math.max(ans, s + Math.abs(nums[0] - nums[i + 1]) -
                              Math.abs(nums[i] - nums[i + 1]));
      ans = Math.max(ans, s + Math.abs(nums[n - 1] - nums[i]) -
                              Math.abs(nums[i] - nums[i + 1]));
    }
    int[] dirs = {1, -1, -1, 1, 1};
    final int inf = 1 << 30;
    for (int k = 0; k < 4; ++k) {
      int k1 = dirs[k], k2 = dirs[k + 1];
      int mx = -inf, mi = inf;
      for (int i = 0; i < n - 1; ++i) {
        int a = k1 * nums[i] + k2 * nums[i + 1];
        int b = Math.abs(nums[i] - nums[i + 1]);
        mx = Math.max(mx, a - b);
        mi = Math.min(mi, a + b);
      }
      ans = Math.max(ans, s + Math.max(0, mx - mi));
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxValueAfterReverse(vector<int> &nums) {
    int n = nums.size();
    int s = 0;
    for (int i = 0; i < n - 1; ++i) {
      s += abs(nums[i] - nums[i + 1]);
    }
    int ans = s;
    for (int i = 0; i < n - 1; ++i) {
      ans =
          max(ans, s + abs(nums[0] - nums[i + 1]) - abs(nums[i] - nums[i + 1]));
      ans =
          max(ans, s + abs(nums[n - 1] - nums[i]) - abs(nums[i] - nums[i + 1]));
    }
    int dirs[5] = {1, -1, -1, 1, 1};
    const int inf = 1 << 30;
    for (int k = 0; k < 4; ++k) {
      int k1 = dirs[k], k2 = dirs[k + 1];
      int mx = -inf, mi = inf;
      for (int i = 0; i < n - 1; ++i) {
        int a = k1 * nums[i] + k2 * nums[i + 1];
        int b = abs(nums[i] - nums[i + 1]);
        mx = max(mx, a - b);
        mi = min(mi, a + b);
      }
      ans = max(ans, s + max(0, mx - mi));
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxValueAfterReverse(self, nums: List[int]) -> int: ans = s = sum(abs(x - y) for x, y in pairwise(nums)) for x, y in pairwise(nums): ans = max(ans, s + abs(nums[0] - y) - abs(x - y)) ans = max(ans, s + abs(nums[- 1] - x) - abs(x - y)) for k1, k2 in pairwise((1, - 1, - 1, 1, 1)): mx, mi = - inf, inf for x, y in pairwise(nums): a = k1 * x + k2 * y b = abs(x - y) mx = max(mx, a - b) mi = min(mi, a + b) ans = max(ans, s + max(mx - mi, 0)) return ans

```