Watch 3 video solutions for Reverse Subarray To Maximize Array Value, a hard level problem involving Array, Math, Greedy. This walkthrough by Fearless Learner has 1,062 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 105Problem 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 | 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 |