Scale Engineer

Reverse Subarray To Maximize Array Value

Hard
#1236Time: O(N³), where N is the number of elements in the array. There are O(N²) possible subarrays. For each, copying the array takes O(N), reversing takes O(j-i) which is O(N), and calculating the new value takes O(N). This leads to an overall complexity of O(N² * N) = O(N³).Space: O(N), where N is the number of elements in the array. This is for storing the temporary copy of the array in each iteration.
Patterns
MathGreedy
Data structures
Array

Prompt

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.

Approaches

3 approaches with complexity analysis and trade-offs.

The most straightforward approach is to simulate the process directly. We can try reversing every possible subarray, calculate the resulting array's value, and keep track of the maximum value seen. This involves three nested loops: two to define the subarray's start and end points, and a third to calculate the value of the array after the reversal.

Algorithm

  1. Initialize maxValue to 0.
  2. Generate every possible subarray nums[i...j] by iterating i from 0 to n-1 and j from i to n-1.
  3. For each subarray: a. Create a temporary copy of the nums array. b. Reverse the subarray from index i to j in the temporary array. c. Calculate the 'value' of this modified temporary array by summing the absolute differences of adjacent elements: sum(|temp[k] - temp[k+1]|). d. Update maxValue = max(maxValue, calculated_value).
  4. Return maxValue.

Walkthrough

This brute-force method iterates through all possible start (i) and end (j) indices of a subarray. For each subarray nums[i...j], it creates a copy of the original array, performs the reversal on the copy, and then computes the value of the new array from scratch. The value is the sum of absolute differences of adjacent elements. The maximum value found across all possible reversals is the answer.

class Solution {    public int maxValueAfterReverse(int[] nums) {        int n = nums.length;        int maxVal = 0;         // Calculate initial value to handle the case of no reversal (or reversing a single element)        for (int i = 0; i < n - 1; i++) {            maxVal += Math.abs(nums[i] - nums[i + 1]);        }         for (int i = 0; i < n; i++) {            for (int j = i; j < n; j++) {                // Create a temporary array and reverse the subarray [i, j]                int[] temp = new int[n];                System.arraycopy(nums, 0, temp, 0, n);                reverse(temp, i, j);                 // Calculate the value of the new array                int currentVal = 0;                for (int k = 0; k < n - 1; k++) {                    currentVal += Math.abs(temp[k] - temp[k + 1]);                }                maxVal = Math.max(maxVal, currentVal);            }        }        return maxVal;    }     private void reverse(int[] arr, int start, int end) {        while (start < end) {            int temp = arr[start];            arr[start] = arr[end];            arr[end] = temp;            start++;            end--;        }    }}

Complexity

Time

O(N³), where N is the number of elements in the array. There are O(N²) possible subarrays. For each, copying the array takes O(N), reversing takes O(j-i) which is O(N), and calculating the new value takes O(N). This leads to an overall complexity of O(N² * N) = O(N³).

Space

O(N), where N is the number of elements in the array. This is for storing the temporary copy of the array in each iteration.

Trade-offs

Pros

  • Simple to understand and implement.

Cons

  • Extremely inefficient due to its cubic time complexity.

  • Not feasible for the given constraints on the input size (n up to 3 * 10^4).

Solutions

class Solution {public  int maxValueAfterReverse(int[] nums) {    int n = nums.length;    int s = 0;    for (int i = 0; i < n - 1; ++i) {      s += Math.abs(nums[i] - nums[i + 1]);    }    int ans = s;    for (int i = 0; i < n - 1; ++i) {      ans = Math.max(ans, s + Math.abs(nums[0] - nums[i + 1]) -                              Math.abs(nums[i] - nums[i + 1]));      ans = Math.max(ans, s + Math.abs(nums[n - 1] - nums[i]) -                              Math.abs(nums[i] - nums[i + 1]));    }    int[] dirs = {1, -1, -1, 1, 1};    final int inf = 1 << 30;    for (int k = 0; k < 4; ++k) {      int k1 = dirs[k], k2 = dirs[k + 1];      int mx = -inf, mi = inf;      for (int i = 0; i < n - 1; ++i) {        int a = k1 * nums[i] + k2 * nums[i + 1];        int 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;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem