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.
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.
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.
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.
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 | 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. |
| 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 |
Leetcode 1330. Reverse Subarray To Maximize Array Value • Fearless Learner • 1,062 views views
Watch 2 more video solutions →Practice Reverse Subarray To Maximize Array Value with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor