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.

Examples

Example 1

1
2
3

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

1
2

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

Constraints

  • 2 <= nums.length <= 3 * 10^4
  • -10^5 <= nums[i] <= 10^5
  • The answer is guaranteed to fit in a 32-bit integer.

Solution

Method 1 - Greedy Edge Swap and Min/Max

Intuition

Reversing a subarray can only affect the edges of the subarray. The best gain is achieved by maximizing the difference at the subarray’s new edges. We can try all possible subarrays that start or end at the array’s ends, and also consider the best possible gain by swapping the two edges in the middle.

Approach

First, compute the original value. Then, for each possible subarray, calculate the gain if we reverse it. The best gain is either by reversing a subarray that starts or ends at the array’s ends, or by maximizing the difference between the min and max of adjacent pairs. We track the minimum and maximum of min(nums[i], nums[i+1]) and max(nums[i], nums[i+1]) for all i, and use them to compute the best possible gain.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    int maxValueAfterReverse(vector<int>& nums) {
        int n = nums.size();
        int base = 0;
        for (int i = 0; i < n-1; ++i) base += abs(nums[i] - nums[i+1]);
        int res = base;
        int mx = 0, mn = 1e9;
        for (int i = 1; i < n-1; ++i) {
            mx = max(mx, min(nums[i], nums[i+1]));
            mn = min(mn, max(nums[i], nums[i+1]));
        }
        if (mx < mn) res = max(res, base + 2*(mn - mx));
        for (int i = 1; i < n-1; ++i) {
            res = max(res, base + abs(nums[0] - nums[i+1]) - abs(nums[i] - nums[i+1]));
            res = max(res, base + abs(nums[n-1] - nums[i-1]) - abs(nums[i] - nums[i-1]));
        }
        return res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

import "math"
func maxValueAfterReverse(nums []int) int {
    n := len(nums)
    base := 0
    for i := 0; i < n-1; i++ {
        base += abs(nums[i] - nums[i+1])
    }
    res := base
    mx, mn := 0, math.MaxInt32
    for i := 1; i < n-1; i++ {
        mx = max(mx, min(nums[i], nums[i+1]))
        mn = min(mn, max(nums[i], nums[i+1]))
    }
    if mx < mn {
        res = max(res, base+2*(mn-mx))
    }
    for i := 1; i < n-1; i++ {
        res = max(res, base+abs(nums[0]-nums[i+1])-abs(nums[i]-nums[i+1]))
        res = max(res, base+abs(nums[n-1]-nums[i-1])-abs(nums[i]-nums[i-1]))
    }
    return res
}
func abs(x int) int { if x < 0 { return -x }; return x }
func min(a, b int) int { if a < b { return a }; return b }
func max(a, b int) int { if a > b { return a }; return b }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int maxValueAfterReverse(int[] nums) {
        int n = nums.length, base = 0;
        for (int i = 0; i < n-1; i++) base += Math.abs(nums[i] - nums[i+1]);
        int res = base, mx = 0, mn = Integer.MAX_VALUE;
        for (int i = 1; i < n-1; i++) {
            mx = Math.max(mx, Math.min(nums[i], nums[i+1]));
            mn = Math.min(mn, Math.max(nums[i], nums[i+1]));
        }
        if (mx < mn) res = Math.max(res, base + 2*(mn - mx));
        for (int i = 1; i < n-1; i++) {
            res = Math.max(res, base + Math.abs(nums[0] - nums[i+1]) - Math.abs(nums[i] - nums[i+1]));
            res = Math.max(res, base + Math.abs(nums[n-1] - nums[i-1]) - Math.abs(nums[i] - nums[i-1]));
        }
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    fun maxValueAfterReverse(nums: IntArray): Int {
        val n = nums.size
        var base = 0
        for (i in 0 until n-1) base += kotlin.math.abs(nums[i] - nums[i+1])
        var res = base
        var mx = 0
        var mn = Int.MAX_VALUE
        for (i in 1 until n-1) {
            mx = maxOf(mx, minOf(nums[i], nums[i+1]))
            mn = minOf(mn, maxOf(nums[i], nums[i+1]))
        }
        if (mx < mn) res = maxOf(res, base + 2*(mn - mx))
        for (i in 1 until n-1) {
            res = maxOf(res, base + kotlin.math.abs(nums[0] - nums[i+1]) - kotlin.math.abs(nums[i] - nums[i+1]))
            res = maxOf(res, base + kotlin.math.abs(nums[n-1] - nums[i-1]) - kotlin.math.abs(nums[i] - nums[i-1]))
        }
        return res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def maxValueAfterReverse(self, nums: list[int]) -> int:
        n = len(nums)
        base = sum(abs(nums[i] - nums[i+1]) for i in range(n-1))
        res = base
        mx, mn = 0, float('inf')
        for i in range(1, n-1):
            mx = max(mx, min(nums[i], nums[i+1]))
            mn = min(mn, max(nums[i], nums[i+1]))
        if mx < mn:
            res = max(res, base + 2*(mn - mx))
        for i in range(1, n-1):
            res = max(res, base + abs(nums[0] - nums[i+1]) - abs(nums[i] - nums[i+1]))
            res = max(res, base + abs(nums[n-1] - nums[i-1]) - abs(nums[i] - nums[i-1]))
        return res
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

impl Solution {
    pub fn max_value_after_reverse(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut base = 0;
        for i in 0..n-1 { base += (nums[i] - nums[i+1]).abs(); }
        let mut res = base;
        let mut mx = 0;
        let mut mn = i32::MAX;
        for i in 1..n-1 {
            mx = mx.max(nums[i].min(nums[i+1]));
            mn = mn.min(nums[i].max(nums[i+1]));
        }
        if mx < mn { res = res.max(base + 2*(mn - mx)); }
        for i in 1..n-1 {
            res = res.max(base + (nums[0] - nums[i+1]).abs() - (nums[i] - nums[i+1]).abs());
            res = res.max(base + (nums[n-1] - nums[i-1]).abs() - (nums[i] - nums[i-1]).abs());
        }
        res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

function maxValueAfterReverse(nums: number[]): number {
    const n = nums.length;
    let base = 0;
    for (let i = 0; i < n-1; i++) base += Math.abs(nums[i] - nums[i+1]);
    let res = base, mx = 0, mn = Infinity;
    for (let i = 1; i < n-1; i++) {
        mx = Math.max(mx, Math.min(nums[i], nums[i+1]));
        mn = Math.min(mn, Math.max(nums[i], nums[i+1]));
    }
    if (mx < mn) res = Math.max(res, base + 2*(mn - mx));
    for (let i = 1; i < n-1; i++) {
        res = Math.max(res, base + Math.abs(nums[0] - nums[i+1]) - Math.abs(nums[i] - nums[i+1]));
        res = Math.max(res, base + Math.abs(nums[n-1] - nums[i-1]) - Math.abs(nums[i] - nums[i-1]));
    }
    return res;
}

Complexity

  • ⏰ Time complexity: O(n) — single pass for base, and a few more passes for min/max and edge swaps.
  • 🧺 Space complexity: O(1) — only a few variables are used.