Reverse Subarray To Maximize Array Value solution and explanation
3 more videos on this problem
[LeeCode] BiWeekly 18, #1330-1331Lee215 Code · 16:24 · 1K views
Leetcode 1330. Reverse Subarray To Maximize Array ValueFearless Learner · 24:26 · 1K views
[LeetCode] 1330. Reverse Subarray To Maximize Array Value (Hard)개발자영맨(bluedawnstar) · 31:33 · 860 views
LeetCode Hard: 1330. Reverse Subarray To Maximize Array Valuerobzingcod · 50:54 · 539 views
The 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.
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.
def maxArrayValueAfterReverse(nums):
base_value = 0
max_increment = 0
min_tail_diff = float('inf')
max_tail_diff = -float('inf')
for i in range(len(nums) - 1):
diff = abs(nums[i] - nums[i + 1])
base_value += diff
min_tail_diff = min(min_tail_diff, max(nums[i], nums[i + 1]))
max_tail_diff = max(max_tail_diff, min(nums[i], nums[i + 1]))
for i in range(len(nums) - 1):
max_increment = max(max_increment, abs(nums[0] - nums[i + 1]) - abs(nums[i] - nums[i + 1]))
max_increment = max(max_increment, abs(nums[len(nums) - 1] - nums[i]) - abs(nums[i] - nums[i + 1]))
max_change = 2 * (max_tail_diff - min_tail_diff)
return base_value + max(max_increment, max_change)
# Example Usage
nums = [2, 3, 1, 5, 4]
print(maxArrayValueAfterReverse(nums))public class MaxArrayValue {
public int maxArrayValueAfterReverse(int[] nums) {
int baseValue = 0;
int maxIncrement = 0;
int minTailDiff = Integer.MAX_VALUE;
int maxTailDiff = Integer.MIN_VALUE;
for (int i = 0; i < nums.length - 1; ++i) {
int diff = Math.abs(nums[i] - nums[i + 1]);
baseValue += diff;
minTailDiff = Math.min(minTailDiff, Math.max(nums[i], nums[i + 1]));
maxTailDiff = Math.max(maxTailDiff, Math.min(nums[i], nums[i + 1]));
}
for (int i = 0; i < nums.length - 1; ++i) {
maxIncrement = Math.max(maxIncrement, Math.abs(nums[0] - nums[i + 1]) - Math.abs(nums[i] - nums[i + 1]));
maxIncrement = Math.max(maxIncrement, Math.abs(nums[nums.length - 1] - nums[i]) - Math.abs(nums[i] - nums[i + 1]));
}
int maxChange = 2 * (maxTailDiff - minTailDiff);
return baseValue + Math.max(maxIncrement, maxChange);
}
public static void main(String[] args) {
MaxArrayValue obj = new MaxArrayValue();
int[] nums = {2, 3, 1, 5, 4};
System.out.println(obj.maxArrayValueAfterReverse(nums));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int maxArrayValueAfterReverse(vector<int>& nums) {
int baseValue = 0;
int maxIncrement = 0;
int minTailDiff = INT_MAX;
int maxTailDiff = INT_MIN;
for (int i = 0; i < nums.size() - 1; ++i) {
int diff = abs(nums[i] - nums[i + 1]);
baseValue += diff;
minTailDiff = min(minTailDiff, max(nums[i], nums[i + 1]));
maxTailDiff = max(maxTailDiff, min(nums[i], nums[i + 1]));
}
for (int i = 0; i < nums.size() - 1; ++i) {
maxIncrement = max(maxIncrement, abs(nums[0] - nums[i + 1]) - abs(nums[i] - nums[i + 1]));
maxIncrement = max(maxIncrement, abs(nums[nums.size() - 1] - nums[i]) - abs(nums[i] - nums[i + 1]));
}
int maxChange = 2 * (maxTailDiff - minTailDiff);
return baseValue + max(maxIncrement, maxChange);
}
int main() {
vector<int> nums = {2, 3, 1, 5, 4};
cout << maxArrayValueAfterReverse(nums) << endl;
return 0;
}function maxArrayValueAfterReverse(nums) {
let baseValue = 0;
let maxIncrement = 0;
let minTailDiff = Infinity;
let maxTailDiff = -Infinity;
for (let i = 0; i < nums.length - 1; i++) {
const diff = Math.abs(nums[i] - nums[i + 1]);
baseValue += diff;
minTailDiff = Math.min(minTailDiff, Math.max(nums[i], nums[i + 1]));
maxTailDiff = Math.max(maxTailDiff, Math.min(nums[i], nums[i + 1]));
}
for (let i = 0; i < nums.length - 1; i++) {
maxIncrement = Math.max(maxIncrement, Math.abs(nums[0] - nums[i + 1]) - Math.abs(nums[i] - nums[i + 1]));
maxIncrement = Math.max(maxIncrement, Math.abs(nums[nums.length - 1] - nums[i]) - Math.abs(nums[i] - nums[i + 1]));
}
const maxChange = 2 * (maxTailDiff - minTailDiff);
return baseValue + Math.max(maxIncrement, maxChange);
}
// Example usage
const nums = [2, 3, 1, 5, 4];
console.log(maxArrayValueAfterReverse(nums));#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int maxArrayValueAfterReverse(int* nums, int numsSize) {
int baseValue = 0;
int maxIncrement = 0;
int minTailDiff = INT_MAX;
int maxTailDiff = INT_MIN;
for (int i = 0; i < numsSize - 1; ++i) {
int diff = abs(nums[i] - nums[i + 1]);
baseValue += diff;
minTailDiff = fmin(minTailDiff, fmax(nums[i], nums[i + 1]));
maxTailDiff = fmax(maxTailDiff, fmin(nums[i], nums[i + 1]));
}
for (int i = 0; i < numsSize - 1; ++i) {
maxIncrement = fmax(maxIncrement, abs(nums[0] - nums[i + 1]) - abs(nums[i] - nums[i + 1]));
maxIncrement = fmax(maxIncrement, abs(nums[numsSize - 1] - nums[i]) - abs(nums[i] - nums[i + 1]));
}
int maxChange = 2 * (maxTailDiff - minTailDiff);
return baseValue + fmax(maxIncrement, maxChange);
}
int main() {
int nums[] = {2, 3, 1, 5, 4};
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", maxArrayValueAfterReverse(nums, numsSize));
return 0;
}using System;
public class MaxArrayValue {
public int MaxArrayValueAfterReverse(int[] nums) {
int baseValue = 0;
int maxIncrement = 0;
int minTailDiff = int.MaxValue;
int maxTailDiff = int.MinValue;
for (int i = 0; i < nums.Length - 1; i++) {
int diff = Math.Abs(nums[i] - nums[i + 1]);
baseValue += diff;
minTailDiff = Math.Min(minTailDiff, Math.Max(nums[i], nums[i + 1]));
maxTailDiff = Math.Max(maxTailDiff, Math.Min(nums[i], nums[i + 1]));
}
for (int i = 0; i < nums.Length - 1; i++) {
maxIncrement = Math.Max(maxIncrement, Math.Abs(nums[0] - nums[i + 1]) - Math.Abs(nums[i] - nums[i + 1]));
maxIncrement = Math.Max(maxIncrement, Math.Abs(nums[nums.Length - 1] - nums[i]) - Math.Abs(nums[i] - nums[i + 1]));
}
int maxChange = 2 * (maxTailDiff - minTailDiff);
return baseValue + Math.Max(maxIncrement, maxChange);
}
public static void Main(string[] args) {
MaxArrayValue obj = new MaxArrayValue();
int[] nums = { 2, 3, 1, 5, 4 };
Console.WriteLine(obj.MaxArrayValueAfterReverse(nums));
}
}The solution computes the default array value and evaluates the effect of reversing subarrays by assessing boundary effects. Adjusts value based on extending boundaries of the reversed segment while accounting for initial value.
Time Complexity: O(n) since it operates through the array in a linear pass to determine value adjustments.
Space Complexity: O(1) owing to variable storage for computations.
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.
def calculate_value(nums):
return sum(abs(nums[i] - nums[i+1]) for i in range(len(nums) - 1))
def max_array_value_after_reverse(nums):
original_value = calculate_value(nums)
max_value = original_value
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
nums[i:j+1] = nums[i:j+1][::-1]
new_value = calculate_value(nums)
if new_value > max_value:
max_value = new_value
nums[i:j+1] = nums[i:j+1][::-1] # Reverse back to original
return max_value
# Example usage
nums = [2, 3, 1, 5, 4]
print(max_array_value_after_reverse(nums))import java.util.Arrays;
public class MaxArrayValueBF {
private int calculateValue(int[] nums) {
int result = 0;
for (int i = 0; i < nums.length - 1; ++i) {
result += Math.abs(nums[i] - nums[i + 1]);
}
return result;
}
private void reverse(int[] nums, int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start++] = nums[end];
nums[end--] = temp;
}
}
public int maxArrayValueAfterReverse(int[] nums) {
int originalValue = calculateValue(nums);
int maxValue = originalValue;
for (int i = 0; i < nums.length; ++i) {
for (int j = i + 1; j < nums.length; ++j) {
reverse(nums, i, j);
int newValue = calculateValue(nums);
if (newValue > maxValue) {
maxValue = newValue;
}
reverse(nums, i, j); // Restore original order
}
}
return maxValue;
}
public static void main(String[] args) {
MaxArrayValueBF obj = new MaxArrayValueBF();
int[] nums = {2, 3, 1, 5, 4};
System.out.println(obj.maxArrayValueAfterReverse(nums));
}
}#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;
int calculateValue(const vector<int>& nums) {
int result = 0;
for (int i = 0; i < nums.size() - 1; ++i) {
result += abs(nums[i] - nums[i + 1]);
}
return result;
}
void reverse(vector<int>& nums, int start, int end) {
while (start < end) {
swap(nums[start++], nums[end--]);
}
}
int maxArrayValueAfterReverse(vector<int>& nums) {
int originalValue = calculateValue(nums);
int maxValue = originalValue;
for (int i = 0; i < nums.size(); ++i) {
for (int j = i + 1; j < nums.size(); ++j) {
reverse(nums, i, j);
int newValue = calculateValue(nums);
maxValue = max(maxValue, newValue);
reverse(nums, i, j); // Reverse back to original
}
}
return maxValue;
}
int main() {
vector<int> nums = {2, 3, 1, 5, 4};
cout << maxArrayValueAfterReverse(nums) << endl;
return 0;
}function calculateValue(nums) {
let result = 0;
for (let i = 0; i < nums.length - 1; i++) {
result += Math.abs(nums[i] - nums[i + 1]);
}
return result;
}
function reverse(nums, start, end) {
while (start < end) {
let temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}
function maxArrayValueAfterReverse(nums) {
const originalValue = calculateValue(nums);
let maxValue = originalValue;
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
reverse(nums, i, j);
const newValue = calculateValue(nums);
if (newValue > maxValue) {
maxValue = newValue;
}
reverse(nums, i, j); // Reverse back to original
}
}
return maxValue;
}
// Example usage
const nums = [2, 3, 1, 5, 4];
console.log(maxArrayValueAfterReverse(nums));#include <stdio.h>
#include <stdlib.h>
int calculateValue(int* nums, int numsSize) {
int result = 0;
for (int i = 0; i < numsSize - 1; ++i) {
result += abs(nums[i] - nums[i + 1]);
}
return result;
}
void reverse(int* nums, int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start++] = nums[end];
nums[end--] = temp;
}
}
int maxArrayValueAfterReverse(int* nums, int numsSize) {
int originalValue = calculateValue(nums, numsSize);
int maxValue = originalValue;
for (int i = 0; i < numsSize; ++i) {
for (int j = i + 1; j < numsSize; ++j) {
reverse(nums, i, j);
int newValue = calculateValue(nums, numsSize);
maxValue = (newValue > maxValue) ? newValue : maxValue;
reverse(nums, i, j); // Reverse back to original
}
}
return maxValue;
}
int main() {
int nums[] = {2, 3, 1, 5, 4};
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", maxArrayValueAfterReverse(nums, numsSize));
return 0;
}using System;
public class MaxArrayValueBF {
private int CalculateValue(int[] nums) {
int result = 0;
for (int i = 0; i < nums.Length - 1; ++i) {
result += Math.Abs(nums[i] - nums[i + 1]);
}
return result;
}
private void Reverse(int[] nums, int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start++] = nums[end];
nums[end--] = temp;
}
}
public int MaxArrayValueAfterReverse(int[] nums) {
int originalValue = CalculateValue(nums);
int maxValue = originalValue;
for (int i = 0; i < nums.Length; i++) {
for (int j = i + 1; j < nums.Length; j++) {
Reverse(nums, i, j);
int newValue = CalculateValue(nums);
if (newValue > maxValue) {
maxValue = newValue;
}
Reverse(nums, i, j); // Restore original order
}
}
return maxValue;
}
public static void Main(string[] args) {
MaxArrayValueBF obj = new MaxArrayValueBF();
int[] nums = { 2, 3, 1, 5, 4 };
Console.WriteLine(obj.MaxArrayValueAfterReverse(nums));
}
}This function employs a methodic test of all subarray reversals, determining the maximal value enhancement derivable from any single reversal. Cumbersome for substantial arrays since computation unnecessarily exhausts all possibilities.
Time Complexity: O(n^3), aggravated by iterating over subarrays and recalculating their values.
Space Complexity: O(1) notwithstanding fixed temporary storage demands intrinsic to arithmetic progress.
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:
function maxValueAfterReverse(nums: number[]): number {
const n = nums.length;
let s = 0;
for (let i = 0; i < n - 1; ++i) {
s += Math.abs(nums[i] - nums[i + 1]);
}
let ans = s;
for (let i = 0; i < n - 1; ++i) {
const d = Math.abs(nums[i] - nums[i + 1]);
ans = Math.max(ans, s + Math.abs(nums[0] - nums[i + 1]) - d);
ans = Math.max(ans, s + Math.abs(nums[n - 1] - nums[i]) - d);
}
const dirs = [1, -1, -1, 1, 1];
const inf = 1 << 30;
for (let k = 0; k < 4; ++k) {
let mx = -inf;
let mi = inf;
for (let i = 0; i < n - 1; ++i) {
const a = dirs[k] * nums[i] + dirs[k + 1] * nums[i + 1];
const b = Math.abs(nums[i] - nums[i + 1]);
mx = Math.max(mx, a - b);
mi = Math.min(mi, a + b);
}
ans = Math.max(ans, s + Math.max(0, mx - mi));
}
return ans;
}func maxValueAfterReverse(nums []int) int {
s, n := 0, len(nums)
for i, x := range nums[:n-1] {
y := nums[i+1]
s += abs(x - y)
}
ans := s
for i, x := range nums[:n-1] {
y := nums[i+1]
ans = max(ans, s+abs(nums[0]-y)-abs(x-y))
ans = max(ans, s+abs(nums[n-1]-x)-abs(x-y))
}
dirs := [5]int{1, -1, -1, 1, 1}
const inf = 1 << 30
for k := 0; k < 4; k++ {
k1, k2 := dirs[k], dirs[k+1]
mx, mi := -inf, inf
for i, x := range nums[:n-1] {
y := nums[i+1]
a := k1*x + k2*y
b := abs(x - y)
mx = max(mx, a-b)
mi = min(mi, a+b)
}
ans = max(ans, s+max(mx-mi, 0))
}
return ans
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach to Maximize Increment | Time Complexity: O(n) since it operates through the array in a linear pass to determine value adjustments. |
| Brute Force Approach | Time Complexity: O(n^3), aggravated by iterating over subarrays and recalculating their values. |
| Classification Discussion + Enumeration | – |
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 |
Frequently asked questions
Is Reverse Subarray To Maximize Array Value easy or hard?
Reverse Subarray To Maximize Array Value is classified as a Hard problem. The difficulty comes from recognizing that reversing a subarray only changes boundary contributions and deriving a greedy O(n) strategy instead of simulating all O(n^2) reversals.
Reverse Subarray To Maximize Array Value Python/Java solution
The greedy O(n) approach works the same across languages such as Python, Java, C++, C#, and JavaScript. Implement a single pass to compute the base value, then track the best gain from prefix, suffix, and middle reversals before returning the maximum total.
How to solve Reverse Subarray To Maximize Array Value in O(n)?
Compute the base value of the array as the sum of absolute differences between adjacent elements. Then evaluate gains from reversing prefixes, suffixes, and middle segments by analyzing boundary pairs. Track the maximum improvement using greedy comparisons of adjacent pair extremes during a single pass.
What is the best approach for Reverse Subarray To Maximize Array Value?
The best approach is a greedy boundary optimization that runs in O(n) time and O(1) space. First compute the base sum of |nums[i] - nums[i-1]|. Then evaluate how reversing segments affects only boundary pairs and track the maximum possible improvement using local comparisons.
Is Reverse Subarray To Maximize Array Value asked at Google/Amazon/Meta?
Hard array and greedy optimization problems like this commonly appear in interviews at companies such as Google, Amazon, and Meta. The question tests understanding of array transformations, absolute difference properties, and the ability to convert a brute force idea into an O(n) greedy solution.
What data structure is used in Reverse Subarray To Maximize Array Value?
The solution primarily uses arrays with a greedy strategy. No additional complex data structures are required because the optimization relies on analyzing adjacent elements and tracking minimum and maximum boundary values.
What is the time complexity of Reverse Subarray To Maximize Array Value?
The optimal solution runs in O(n) time with O(1) extra space. It computes the initial array value in one pass and then analyzes possible gains from reversing different segments using constant-time updates per element.