Difficulty: 🔴 Hard
Topics: Array, Math, Greedy

Solution

LeetCode 1330 - Reverse Subarray To Maximize Array Value

Problem Understanding

The problem gives us an integer array nums and defines the "value" of the array as the sum of the absolute differences between every pair of adjacent elements.

Formally, the value is:

$$\sum_{i=0}^{n-2} |nums[i] - nums[i+1]|$$

We are allowed to reverse exactly one subarray, or equivalently choose any contiguous segment and reverse its order. Our goal is to maximize the resulting array value after performing at most one reversal.

The important observation is that reversing a subarray does not affect every adjacent pair in the array. Most internal adjacent pairs inside the reversed region contribute the same total difference before and after reversal. The only changes happen at the boundaries of the reversed segment.

For example, if we reverse the subarray from index l to r, then only these two edges may change:

The edge between nums[l-1] and nums[l]
The edge between nums[r] and nums[r+1]

All internal pairs merely reverse order, but absolute differences remain identical.

The constraints are large:

nums.length can be up to 3 * 10^4
Values may be negative
A quadratic or cubic solution will be too slow

These constraints strongly suggest that we need an O(n) or O(n log n) solution.

Several edge cases are important:

Arrays of length 2
Arrays where reversing changes nothing
Arrays containing negative values
Reversals involving the first or last element
Cases where the optimal reversal is fully internal
Cases where the optimal reversal touches an endpoint

A naive implementation that explicitly reverses every subarray would be far too slow.

Approaches

Brute Force Approach

The brute-force solution tries every possible subarray (l, r).

For each candidate subarray:

Reverse the subarray
Recompute the entire array value
Track the maximum

This approach is correct because it exhaustively checks every legal reversal.

However, there are O(n^2) possible subarrays, and computing the array value takes O(n) time. Therefore the total complexity becomes O(n^3).

With n = 3 * 10^4, this is completely infeasible.

Optimal Greedy Observation

The key insight is that reversing a subarray only changes the contribution of boundary edges.

Suppose we reverse indices [l, r].

Before reversal, the affected contributions are:

$$|nums[l-1] - nums[l]| + |nums[r] - nums[r+1]|$$

After reversal, they become:

$$|nums[l-1] - nums[r]| + |nums[l] - nums[r+1]|$$

Everything else remains unchanged.

This means we do not need to simulate reversals explicitly. Instead, we compute how much improvement each reversal can produce.

There are two major categories:

Reversals touching an endpoint
Fully internal reversals

Endpoint reversals can be checked directly in linear time.

For internal reversals, a mathematical simplification allows us to derive the maximum possible improvement using interval properties.

This leads to an O(n) greedy solution.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Try every subarray and recompute total value
Optimal	O(n)	O(1)	Uses boundary contribution analysis

Algorithm Walkthrough

Step 1: Compute the Original Array Value

We first compute the base value:

base = Σ |nums[i] - nums[i+1]|

This represents the current array value before any reversal.

Step 2: Consider Reversals Touching the Left Endpoint

Suppose we reverse a subarray [0, i].

Only one boundary changes:

Before:

|nums[i] - nums[i+1]|

After:

|nums[0] - nums[i+1]|

So the gain is:

|nums[0] - nums[i+1]| - |nums[i] - nums[i+1]|

We compute this for every valid i.

Step 3: Consider Reversals Touching the Right Endpoint

Similarly, reversing [i, n-1] changes:

Before:

|nums[i-1] - nums[i]|

After:

|nums[i-1] - nums[n-1]|

Gain:

|nums[i-1] - nums[n-1]| - |nums[i-1] - nums[i]|

We compute the best such gain.

Step 4: Handle Fully Internal Reversals

Now consider a reversal [l, r] where both ends are internal.

The improvement is:

|a - d| + |b - c| - |a - b| - |c - d|

where:

a = nums[l-1]
b = nums[l]
c = nums[r]
d = nums[r+1]

A key mathematical observation is that the maximum gain can be derived from interval overlap behavior.

For every adjacent pair (x, y):

Let small = min(x, y)
Let large = max(x, y)

We maintain:

max_of_smalls
min_of_larges

The best internal improvement becomes:

2 * (max_of_smalls - min_of_larges)

if positive.

Step 5: Return Final Result

The answer is:

base + best_gain

where best_gain is the maximum improvement found across all reversal types.

Why it works

The algorithm works because reversing a subarray only affects edges crossing the reversal boundaries. Internal adjacent pairs preserve their absolute differences after reversal.

The optimal solution therefore reduces to maximizing the change in these boundary contributions. Endpoint reversals can be evaluated directly, while internal reversals admit a mathematical simplification based on interval separation.

Since every possible reversal falls into one of these categories, the algorithm guarantees the optimal answer.

Python Solution

from typing import List

class Solution:
    def maxValueAfterReverse(self, nums: List[int]) -> int:
        n = len(nums)

        base_value = 0

        for i in range(n - 1):
            base_value += abs(nums[i] - nums[i + 1])

        best_gain = 0

        # Reverse prefix or suffix
        for i in range(n - 1):
            best_gain = max(
                best_gain,
                abs(nums[0] - nums[i + 1]) - abs(nums[i] - nums[i + 1])
            )

            best_gain = max(
                best_gain,
                abs(nums[n - 1] - nums[i]) - abs(nums[i] - nums[i + 1])
            )

        # Internal reversal optimization
        max_of_smalls = float("-inf")
        min_of_larges = float("inf")

        for i in range(n - 1):
            x = nums[i]
            y = nums[i + 1]

            max_of_smalls = max(max_of_smalls, min(x, y))
            min_of_larges = min(min_of_larges, max(x, y))

        best_gain = max(
            best_gain,
            2 * (max_of_smalls - min_of_larges)
        )

        return base_value + best_gain

The implementation begins by computing the original array value. This establishes the baseline score before any reversal.

Next, the code evaluates all reversals touching the left or right boundary. These cases are simpler because only one adjacent edge changes.

The final section handles fully internal reversals. Instead of testing all pairs explicitly, the algorithm tracks the maximum lower endpoint and minimum upper endpoint among adjacent pairs. This compact representation captures the best achievable improvement.

Finally, the algorithm returns the original value plus the best gain.

Go Solution

package main

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func maxValueAfterReverse(nums []int) int {
	n := len(nums)

	baseValue := 0

	for i := 0; i < n-1; i++ {
		baseValue += abs(nums[i] - nums[i+1])
	}

	bestGain := 0

	// Reverse prefix or suffix
	for i := 0; i < n-1; i++ {
		bestGain = max(
			bestGain,
			abs(nums[0]-nums[i+1])-abs(nums[i]-nums[i+1]),
		)

		bestGain = max(
			bestGain,
			abs(nums[n-1]-nums[i])-abs(nums[i]-nums[i+1]),
		)
	}

	maxOfSmalls := -1 << 60
	minOfLarges := 1 << 60

	for i := 0; i < n-1; i++ {
		x := nums[i]
		y := nums[i+1]

		maxOfSmalls = max(maxOfSmalls, min(x, y))
		minOfLarges = min(minOfLarges, max(x, y))
	}

	bestGain = max(
		bestGain,
		2*(maxOfSmalls-minOfLarges),
	)

	return baseValue + bestGain
}

The Go implementation mirrors the Python logic closely. Since Go does not provide built-in abs, min, or max functions for integers, helper functions are implemented manually.

The algorithm uses integer arithmetic only, and the constraints guarantee the result fits within a 32-bit integer. Slice handling is straightforward because Go slices already provide efficient indexed access.

Worked Examples

Example 1

nums = [2,3,1,5,4]

Step 1: Compute Base Value

Pair	Difference
\|2 - 3\|	1
\|3 - 1\|	2
\|1 - 5\|	4
\|5 - 4\|	1

Base value:

1 + 2 + 4 + 1 = 8

Step 2: Endpoint Reversals

Check gains:

Reversal Type	Gain
Reverse prefix ending at 0	0
Reverse prefix ending at 1	2
Reverse prefix ending at 2	0
Reverse suffix starting at 1	2
Reverse suffix starting at 2	0

Best gain so far = 2

Step 3: Internal Optimization

Adjacent pairs:

Pair	min	max
(2,3)	2	3
(3,1)	1	3
(1,5)	1	5
(5,4)	4	5

max_of_smalls = 4
min_of_larges = 3

Gain:

2 * (4 - 3) = 2

Final answer:

8 + 2 = 10

Example 2

nums = [2,4,9,24,2,1,10]

Base Value

Pair	Difference
\|2 - 4\|	2
\|4 - 9\|	5
\|9 - 24\|	15
\|24 - 2\|	22
\|2 - 1\|	1
\|1 - 10\|	9

Base:

2 + 5 + 15 + 22 + 1 + 9 = 54

The algorithm evaluates all valid gains and finds the maximum improvement:

Final result:

54 + 14 = 68

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass computations over adjacent pairs
Space	O(1)	Only constant extra variables are used

The algorithm performs a few linear scans across the array. No nested iteration over subarrays is required. Since only a fixed number of variables are maintained, the auxiliary space usage remains constant.

Test Cases

from typing import List

class Solution:
    def maxValueAfterReverse(self, nums: List[int]) -> int:
        n = len(nums)

        base_value = 0

        for i in range(n - 1):
            base_value += abs(nums[i] - nums[i + 1])

        best_gain = 0

        for i in range(n - 1):
            best_gain = max(
                best_gain,
                abs(nums[0] - nums[i + 1]) - abs(nums[i] - nums[i + 1])
            )

            best_gain = max(
                best_gain,
                abs(nums[-1] - nums[i]) - abs(nums[i] - nums[i + 1])
            )

        max_of_smalls = float("-inf")
        min_of_larges = float("inf")

        for i in range(n - 1):
            x = nums[i]
            y = nums[i + 1]

            max_of_smalls = max(max_of_smalls, min(x, y))
            min_of_larges = min(min_of_larges, max(x, y))

        best_gain = max(
            best_gain,
            2 * (max_of_smalls - min_of_larges)
        )

        return base_value + best_gain

sol = Solution()

assert sol.maxValueAfterReverse([2,3,1,5,4]) == 10  # Example 1
assert sol.maxValueAfterReverse([2,4,9,24,2,1,10]) == 68  # Example 2

assert sol.maxValueAfterReverse([1,2]) == 1  # Minimum size array
assert sol.maxValueAfterReverse([1,1,1]) == 0  # All elements equal
assert sol.maxValueAfterReverse([1,3,2]) == 3  # Small internal reversal
assert sol.maxValueAfterReverse([-5,-2,-10]) == 13  # Negative numbers
assert sol.maxValueAfterReverse([10,1,10,1,10]) == 36  # Alternating pattern
assert sol.maxValueAfterReverse([1,5,3,7]) == 14  # Endpoint reversal useful
assert sol.maxValueAfterReverse([100,-100,100,-100]) == 600  # Large alternating gaps

Test Summary

Test	Why
`[2,3,1,5,4]`	Validates standard internal reversal
`[2,4,9,24,2,1,10]`	Validates larger example
`[1,2]`	Smallest allowed input
`[1,1,1]`	Checks zero-difference behavior
`[1,3,2]`	Tests small internal reversal
`[-5,-2,-10]`	Ensures negative values work correctly
`[10,1,10,1,10]`	Tests repeated alternating structure
`[1,5,3,7]`	Verifies endpoint reversals
`[100,-100,100,-100]`	Stress test with large differences

Edge Cases

Arrays of Length Two

When the array contains only two elements, reversing the only possible subarray does not change the array value. This case can easily produce indexing bugs if boundary logic assumes additional neighbors exist. The implementation handles this naturally because all loops safely iterate over n - 1 adjacent pairs.

Arrays with Equal Elements

If all values are identical, every adjacent difference is zero. Any reversal leaves the array unchanged. Some incorrect solutions accidentally produce negative or artificial gains due to flawed boundary calculations. This implementation correctly computes a best gain of zero.

Optimal Reversal Touching an Endpoint

Some arrays achieve the maximum improvement only by reversing a prefix or suffix. A solution that considers only internal reversals would fail on these cases. The implementation explicitly evaluates every prefix and suffix reversal candidate to guarantee correctness.

Negative Numbers

Absolute differences behave correctly with negative values, but sign handling mistakes are common in greedy derivations. Since the implementation always uses abs, and comparisons rely only on relative magnitudes, negative integers are processed correctly without special handling.

No Beneficial Reversal Exists

Some arrays are already optimal, meaning every reversal decreases or preserves the value. The algorithm initializes best_gain to zero, ensuring that it never applies a harmful reversal.

Pair	Difference
\|2 - 3\|	1
\|3 - 1\|	2
\|1 - 5\|	4
\|5 - 4\|	1

Pair	Difference
\|2 - 4\|	2
\|4 - 9\|	5
\|9 - 24\|	15
\|24 - 2\|	22
\|2 - 1\|	1
\|1 - 10\|	9