Reverse Subarray To Maximize Array Value - Solution & Explanation
Problem Statement
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.
Approach Overview
Problem Overview: You are given an array where the value of the array is defined as sum(|nums[i] - nums[i-1]|). You may reverse exactly one subarray. The goal is to maximize the total array value after the reversal.
Approach 1: Brute Force Subarray Reversal (O(n^3) time, O(1) space)
The most direct strategy is to try every possible subarray [l, r], reverse it, and recompute the total array value. Computing the value requires iterating through the entire array and summing |nums[i] - nums[i-1]|. Since there are O(n^2) possible subarrays and each evaluation costs O(n), the total complexity becomes O(n^3). This approach is useful for understanding how reversal affects adjacent absolute differences, but it quickly becomes too slow for large inputs. It mainly serves as a conceptual baseline before optimizing.
Approach 2: Greedy Boundary Optimization (O(n) time, O(1) space)
The key observation is that reversing a subarray only changes the contributions at the boundaries of that subarray. The internal elements keep the same pairwise absolute differences because their order simply flips. Start by computing the base value of the array using a single pass. Then analyze how reversing different segments affects only the edges: specifically pairs involving nums[l-1], nums[l], nums[r], and nums[r+1]. By checking reversals that include the first or last element, you can compute potential gains directly.
For middle segments, track the maximum possible improvement by comparing extreme values of adjacent pairs. Maintain the minimum of the larger values and the maximum of the smaller values among neighboring pairs. This greedy observation captures the best gain achievable by reversing a middle segment without enumerating every pair. Combining these improvements with the base value yields the optimal answer in a single pass.
This technique relies on properties of absolute differences and careful boundary analysis rather than simulating reversals. It fits naturally with array traversal patterns and uses a greedy strategy supported by simple math observations.
Recommended for interviews: The greedy boundary optimization is the expected solution. Interviewers want to see whether you recognize that reversing a segment only changes a constant number of boundary terms. Starting with the brute force explanation shows understanding of the operation, but deriving the O(n) greedy improvement demonstrates strong problem-solving ability.
Approach 1: Greedy Approach to Maximize Increment
This approach involves reversing a subarray to maximize the increase in the array's value where each boundary of the subarray is analyzed to gauge potential increases in the value.
The function calculates the base value of the array and looks for potential increments. It checks differences at the boundary of the array reversed over. The main goal is to capture the maximum possible benefit of a reverse operation across possible subarray boundaries.
Complexity
Time Complexity: O(n), where n is the length of the array. This is because we need to iterate over the array a constant number of times.
Space Complexity: O(1) since the calculations are done in-place without extra memory apart from a few variables.
Approach 2: Brute Force Approach
This simple approach attempts to reverse every possible subarray and calculates the resulting array's value to identify the maximum possible outcome. While it's not optimal for large inputs, it's a helpful method for understanding the effect of each reversal.
The brute force approach involves iterating over all possible subarrays, reversing them, and evaluating resulting array values to determine the maximum increase as a consequence of any single reversal. Since it tries each subarray, it may become inefficient with large inputs.
Complexity
Time Complexity: O(n^3), due to iterating over every subarray and computing the resultant array value repeatedly.
Space Complexity: O(1) given minimal storage outside of constant variables.
Approach 3: Classification Discussion + Enumeration
According to the problem description, we need to find the maximum value of the array sum_{i=0}^{n-2} |a_i - a_{i+1}| when reversing a subarray once.
Next, we discuss the following cases:
- Do not reverse the subarray.
- Reverse the subarray, and the subarray "includes" the first element.
- Reverse the subarray, and the subarray "includes" the last element.
- Reverse the subarray, and the subarray "does not include" the first and last elements.
Let s be the array value when the subarray is not reversed, then s = sum_{i=0}^{n-2} |a_i - a_{i+1}|. We can initialize the answer ans to s.
If we reverse the subarray and the subarray includes the first element, we can enumerate the last element a_i of the reversed subarray, where 0 leq i < n-1. In this case, ans = max(ans, s + |a_0 - a_{i+1}| - |a_i - a_{i+1}|).
Similarly, if we reverse the subarray and the subarray includes the last element, we can enumerate the first element a_{i+1} of the reversed subarray, where 0 leq i < n-1. In this case, ans = max(ans, s + |a_{n-1} - a_i| - |a_i - a_{i+1}|).
If we reverse the subarray and the subarray does not include the first and last elements, we consider any two adjacent elements in the array as a point pair (x, y). Let the first element of the reversed subarray be y_1, and its left adjacent element be x_1; let the last element of the reversed subarray be x_2, and its right adjacent element be y_2.
At this time, compared to not reversing the subarray, the change in the array value is |x_1 - x_2| + |y_1 - y_2| - |x_1 - y_1| - |x_2 - y_2|, where the first two terms can be expressed as:
$
\left | x_1 - x_2 \right | + \left | y_1 - y_2 \right | = max \begin{cases} (x_1 + y_1) - (x_2 + y_2) \ (x_1 - y_1) - (x_2 - y_2) \ (-x_1 + y_1) - (-x_2 + y_2) \ (-x_1 - y_1) - (-x_2 - y_2) \end{cases}
Then the change in the array value is:
\left | x_1 - x_2 \right | + \left | y_1 - y_2 \right | - \left | x_1 - y_1 \right | - \left | x_2 - y_2 \right | = max \begin{cases} (x_1 + y_1) - \left |x_1 - y_1 \right | - \left ( (x_2 + y_2) + \left |x_2 - y_2 \right | \right ) \ (x_1 - y_1) - \left |x_1 - y_1 \right | - \left ( (x_2 - y_2) + \left |x_2 - y_2 \right | \right ) \ (-x_1 + y_1) - \left |x_1 - y_1 \right | - \left ( (-x_2 + y_2) + \left |x_2 - y_2 \right | \right ) \ (-x_1 - y_1) - \left |x_1 - y_1 \right | - \left ( (-x_2 - y_2) + \left |x_2 - y_2 \right | \right ) \end{cases}
Therefore, we only need to find the maximum value mx of k_1 times x + k_2 times y, where k_1, k_2 \in {-1, 1}, and the corresponding minimum value mi of |x - y|. Then the maximum change in the array value is mx - mi. The answer is ans = max(ans, s + max(0, mx - mi)).
In the code implementation, we define an array of length 5, dirs=[1, -1, -1, 1, 1]. Each time we take two adjacent elements of the array as the values of k_1 and k_2, which can cover all cases of k_1, k_2 \in {-1, 1}.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1)$.
Similar problems:
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Greedy Approach to Maximize Increment | Time Complexity: O(n), where n is the length of the array. This is because we need to iterate over the array a constant number of times. |
| Brute Force Approach | Time Complexity: O(n^3), due to iterating over every subarray and computing the resultant array value repeatedly. |
| Classification Discussion + Enumeration | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subarray Reversal | O(n^3) | O(1) | Good for understanding how reversing affects absolute differences and verifying small test cases |
| Greedy Boundary Optimization | O(n) | O(1) | Best general solution for large inputs and the expected approach in coding interviews |
Video Solution
[LeeCode] BiWeekly 18, #1330-1331 • Lee215 Code • 1,247 views views
Watch 3 more video solutions →Frequently Asked Questions
Is Reverse Subarray To Maximize Array Value easy or hard?
Reverse Subarray To Maximize Array Value Python/Java solution
How to solve Reverse Subarray To Maximize Array Value in O(n)?
What is the best approach for Reverse Subarray To Maximize Array Value?
Is Reverse Subarray To Maximize Array Value asked at Google/Amazon/Meta?
What data structure is used in Reverse Subarray To Maximize Array Value?
What is the time complexity of Reverse Subarray To Maximize Array Value?
Ready to solve this problem?
Practice Reverse Subarray To Maximize Array Value with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor