Problem Explanation

Given an array of integers, the object of this problem is to find the maximum possible value of the array after reversing a subarray once. The value of the array is defined as the sum of the absolute difference between each element and its immediate succeeding element.

Let's illustrate this problem with an example.

If we are given nums = [2,3,1,5,4], by reversing the subarray [3,1,5], our array becomes [2,5,1,3,4]. This array gives the maximum possible value, which is 10 (3 + 4 + 2 + 1).

The chosen reversing subarray can be of any size including the entire array itself. If reversing the subarray doesn't provide any improvements to the array's value, the original array is considered as the result array.

Solution Approach

The approach involves several steps:

1. We first compute the initial sum of absolute differences total of the given array.
2. Then, we find two elements in the array such that they maximize the difference of the new array value and total when reversing the subarray. We use min and max to track the minimum maximum and maximum minimum values.
3. We find the maximal improvement diff for all pairs of elements in the array.
4. The result is total + diff.

C++ Solution

1
2cpp
3class Solution {
4 public:
5  int maxValueAfterReverse(vector<int>& nums) {
6    int total = 0;
7    int min = INT_MAX;
8    int max = INT_MIN;
9
10    for (int i = 0; i + 1 < nums.size(); ++i) {
11      int a = nums[i];
12      int b = nums[i + 1];
13      total += abs(a - b);
14      min = std::min(min, std::max(a, b));
15      max = std::max(max, std::min(a, b));
16    }
17    
18    int diff = std::max(0, (max - min) * 2);  
19
20    for (int i = 0; i + 1 < nums.size(); ++i) {
21      int a = nums[i];
22      int b = nums[i + 1];
23      diff = std::max(diff, abs(nums[0] - b) - abs(a - b));
24      diff = std::max(diff, abs(nums.back() - a) - abs(a - b));
25    }
26  
27    return total + diff;
28  }
29};

In the C++ solution above, we first loop through the array to calculate the total value and find the min and max values. We then iterate through the array a second time to calculate diff.# Python Solution

1
2python
3class Solution:
4    def maxValueAfterReverse(self, nums):
5        total, n = 0, len(nums)
6        
7        min_max, max_min = float('inf'), float('-inf')
8
9        for i in range(n-1):
10            a, b = sorted([nums[i], nums[i+1]])
11            total += abs(a - b)
12            min_max = min(min_max, max(nums[i], nums[i+1]))
13            max_min = max(max_min, min(nums[i], nums[i+1]))
14
15        diff = max(0, (max_min - min_max) * 2)  
16
17        for i in range(n-1):
18            diff = max(diff, abs(nums[0] - nums[i+1]) - abs(nums[i] - nums[i+1]))
19            diff = max(diff, abs(nums[-1] - nums[i]) - abs(nums[i] - nums[i+1]))
20
21        return total + diff

In the Python solution, we replace C++'s INT_MAX and INT_MIN with Python's float('inf') and float('-inf') respectively.

JavaScript Solution

1
2javascript
3function maxValueAfterReverse(nums) {
4    let total = 0;
5    let min_max = Number.MAX_SAFE_INTEGER;
6    let max_min = Number.MIN_SAFE_INTEGER;
7
8    for(let i = 0 ; i + 1 < nums.length ; ++i) {
9        let a = nums[i];
10        let b = nums[i + 1];
11        total += Math.abs(a - b);
12        min_max = Math.min(min_max, Math.max(a, b));
13        max_min = Math.max(max_min, Math.min(a, b));
14    }
15
16    let diff = Math.max(0, (max_min - min_max) * 2);
17
18    for(let i = 0 ; i + 1 < nums.length ; ++i) {
19        let a = nums[i];
20        let b = nums[i + 1];
21        diff = Math.max(diff, Math.abs(nums[0] - b) - Math.abs(a - b));
22        diff = Math.max(diff, Math.abs(nums[nums.length-1] - a) - Math.abs(a - b));
23    }
24
25    return total + diff;
26}

In JavaScript, we replace C++'s INT_MAX and INT_MIN with JavaScript's Number.MAX_SAFE_INTEGER and Number.MIN_SAFE_INTEGER respectively.

Java Solution

1
2java
3class Solution {
4    public int maxValueAfterReverse(int[] nums) {
5        int total = 0;
6        int min_max = Integer.MAX_VALUE;
7        int max_min = Integer.MIN_VALUE;
8
9        for(int i = 0; i + 1 < nums.length; i++) {
10            int a = nums[i];
11            int b = nums[i + 1];
12            total += Math.abs(a - b);
13            min_max = Math.min(min_max, Math.max(a, b));
14            max_min = Math.max(max_min, Math.min(a, b));
15        }
16
17        int diff = Math.max(0, (max_min - min_max) * 2);
18
19        for(int i = 0 ; i + 1 < nums.length; i++) {
20            int a = nums[i];
21            int b = nums[i + 1];
22            diff = Math.max(diff, Math.abs(nums[0] - b) - Math.abs(a - b));
23            diff = Math.max(diff, Math.abs(nums[nums.length-1] - a) - Math.abs(a - b));
24        }
25
26        return total + diff;
27    }
28}

The Java solution uses a similar strategy as the C++ and Python versions but the syntax is different. For example, Java uses Math.max and Math.min functions to calculate the minimum and maximum values. In Java, arrays are also zero-indexed, so the element at the end of the array is accessed with nums[nums.length - 1].