1330. Reverse Subarray To Maximize Array Value


Problem Description

In this problem, we are given an integer array called nums. The value of this array is defined as the sum of the absolute differences between consecutive elements, expressed as |nums[i] - nums[i + 1]| for all 0 <= i < nums.length - 1.

We are allowed to perform one operation on this array: select any subarray and reverse it. The goal is to find the maximum possible value for the array after possibly performing this reversal operation exactly once.

The task is to figure out if reversing a certain subarray can lead to an increase in the total value of the array as defined and, if so, to maximize this value.

Intuition

To solve this problem, we need to consider what happens to the value of the array when we reverse a subarray. Reversing a subarray could potentially increase the total value if the differences between the numbers at the borders of the subarray and the adjacent numbers outside the subarray are increased.

The solution approach involves several parts:

  1. Calculating the initial value (s) of the array, which is the sum of the absolute differences between all consecutive elements. This value is the baseline that we will try to improve with the reversal operation.

  2. Checking if reversing the start or the end of the array with any other element x or y in the array can lead to an increase in value. This means we compare the gains from altering the initial or final elements with each inside pair x, y.

  3. Iterating over the array to find the best possible subarray to reverse that would result in the highest increase in value. We do this by simulating the effects of reversing a subarray on contribution to the value from each pair of numbers. This involves keeping track of the maximum and minimum values possible from the operations considering both scenarios when |nums[0] - y| or |nums[-1] - x| contributes to the overall value increase.

By iteratively updating the maximum answer (ans), the code captures the best possible value that can be achieved by a single reversal of any subarray. The math behind this involves careful consideration of how the absolute value differences change with potential reversals and how this impact can be maximized.

Learn more about Greedy and Math patterns.

Solution Approach

The solution uses a greedy approach to maximize the value of the array by considering the effect of reversing subarrays on the total value. Here's an explanation of the code implementation:

  1. Firstly, the solution calculates the initial total value s of the array as the sum of the absolute differences between all consecutive elements.

    1s = sum(abs(x - y) for x, y in pairwise(nums))

    This is done using a generator expression within the sum function, which iterates pairs of consecutive elements using Python's pairwise utility. The abs function is used to calculate the absolute difference.

  2. The solution then iterates over these pairs again, considering the potential impact of a reversal operation that includes the first or the last element of the array. The goal here is to find if such a reversal can increase the total value by creating a larger difference at the array's ends.

    1for x, y in pairwise(nums):
    2    ans = max(ans, s + abs(nums[0] - y) - abs(x - y))
    3    ans = max(ans, s + abs(nums[-1] - x) - abs(x - y))

    For each adjacent pair, it computes two potential new values for ans considering the reversal of elements at the start or end of the array, and updates ans to the maximum of these values.

  3. In the final part of the solution, the algorithm considers reversing subarrays in the middle of the array and how it affects the total value. It explores flipping the sign of the components of the pairs and then measures the potential increase in the total value that could come from such operations. This part of the solution uses a trick that combines pairs with different signs in order to simulate the effect of a reversal.

    1for k1, k2 in pairwise((1, -1, -1, 1, 1)):
    2    mx, mi = -inf, inf
    3    for x, y in pairwise(nums):
    4        a = k1 * x + k2 * y
    5        b = abs(x - y)
    6        mx = max(mx, a - b)
    7        mi = min(mi, a + b)
    8    ans = max(ans, s + max(mx - mi, 0))

    It uses variables mx and mi to keep track of the maximum and minimum possible values when considering both options of element placement after a reversal. The max(mx - mi, 0) ensures that only positive changes to the total value are considered, and the overall maximum value is updated accordingly.

Overall, the implemented solution methodically tests all possible single reversal operations that could lead to an increase in the total value, ensuring that the maximum possible result is found. Variables mx, mi, and ans are effectively used to measure and track possible improvements to the total value without ever having to perform an actual subarray reversal.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of these pictures shows the visit order of a depth-first search?

Example Walkthrough

Let’s work through the solution approach with a small example and see how it applies. Suppose we are given the following integer array nums:

1nums = [4, 3, 2, 5]
  1. Firstly, we calculate the initial value s of the array, which is the sum of the absolute differences between consecutive elements. In our case:

    1s = |4 - 3| + |3 - 2| + |2 - 5| = 1 + 1 + 3 = 5
  2. Now, we consider the effect of a reversal operation that includes the first or the last element. We iterate over the pairs and calculate the new potential value after such a reversal.

    1For the pair (4, 3):
    2If we reverse this section, we would get the array [3, 4, 2, 5].
    3The new value would be |3 - 4| + |4 - 2| + |2 - 5| = 5, which is not an improvement over s.
    4
    5For the pair (3, 2):
    6If we reverse from the start, we would get [2, 3, 4, 5].
    7The new value would be |2 - 3| + |3 - 4| + |4 - 5| = 3, which is less than s.
    8
    9If we reverse from the end, we would get the array [4, 2, 3, 5].
    10The new value would be |4 - 2| + |2 - 3| + |3 - 5| = 5, which again is not an improvement.
    11
    12For the pair (2, 5):
    13Reversing with the start doesn't change anything since it is already at the end.

    Here, we do not find any improvement, so we continue the search.

  3. For the final part, we consider subarrays in the middle of the array. We try to manipulate the calculations based on possible subarray reversals without actually reversing them.

    1Let's iterate over the pairs and consider the flips in sign for each pair, which simulate the effects of reversals.
    2
    3Examining each element and computing potential value changes (ignoring the sign flips for brevity):
    4
    5mx = max(-inf, 4 - 1, 3 - 1, 2 - 3) = 3
    6mi = min(inf, 4 + 1, 3 + 1, 2 + 3) = 4
    7
    8The potential increase to s is mx - mi, which is 3 - 4 = -1. Since it's not positive, it doesn't improve the current value.
    9
    10If we continue this approach for each possible subarray reversal, we realize that no reversal in the middle improves the value for this particular array.

In this example, the maximum value that can be obtained after reversing any subarray is the same as the initial value s = 5. Therefore, in this case, performing a reversal operation does not lead to an increased total value. The result is that the best strategy for nums would be to leave the array unchanged.

Solution Implementation

1from itertools import pairwise   # pairwise utility from itertools
2from math import inf             # constant for representing infinity
3
4class Solution:
5    def maxValueAfterReverse(self, nums: list[int]) -> int:
6        # Initial total of absolute differences between all adjacent pairs
7        total_difference = sum(abs(x - y) for x, y in pairwise(nums))
8      
9        # Initialize the answer with the initial total difference
10        answer = total_difference
11      
12        # Try reversing from the start and compare the impact on total difference
13        for x, y in pairwise(nums):
14            answer = max(answer, total_difference + abs(nums[0] - y) - abs(x - y))
15            answer = max(answer, total_difference + abs(nums[-1] - x) - abs(x - y))
16          
17        # Check for all possible reversal segments using pairwise comparison
18        for coef1, coef2 in pairwise((1, -1, -1, 1, 1)):
19            max_difference = -inf  # set to negative infinity to find the maximum
20            min_difference = inf   # set to positive infinity to find the minimum
21          
22            # Iterate over all pairwise elements to find the new possible max difference
23            for x, y in pairwise(nums):
24                a = coef1 * x + coef2 * y
25                abs_difference = abs(x - y)
26                max_difference = max(max_difference, a - abs_difference)
27                min_difference = min(min_difference, a + abs_difference)
28          
29            # Calculate the max total difference if this segment was reversed
30            answer = max(answer, total_difference + max(max_difference - min_difference, 0))
31          
32        # Return the maximum value of total difference after any possible reverse operation
33        return answer
34
1class Solution {
2    public int maxValueAfterReverse(int[] nums) {
3        int n = nums.length;
4        // Initialize the starting sum of absolute differences
5        int totalSum = 0;
6        for (int i = 0; i < n - 1; ++i) {
7            totalSum += Math.abs(nums[i] - nums[i + 1]);
8        }
9        // Initialize the answer with the initial total sum
10        int maxSum = totalSum;
11      
12        // Check if reversing subarray starting from the beginning or ending at the end gives better sum
13        for (int i = 0; i < n - 1; ++i) {
14            maxSum = Math.max(maxSum, totalSum + Math.abs(nums[0] - nums[i + 1]) - Math.abs(nums[i] - nums[i + 1]));
15            maxSum = Math.max(maxSum, totalSum + Math.abs(nums[n - 1] - nums[i]) - Math.abs(nums[i] - nums[i + 1]));
16        }
17      
18        // Prepare directions for the operations to be applied
19        int[] directions = {1, -1, -1, 1, 1};
20        // Use infinity to initialize max and min difference
21        final int infinity = Integer.MAX_VALUE;
22        // Check for all four combinations of directions
23        for (int k = 0; k < 4; ++k) {
24            int direction1 = directions[k], direction2 = directions[k + 1];
25            int maxDiff = -infinity, minDiff = infinity;
26            // Traverse and find the maximum and minimum values accordingly
27            for (int i = 0; i < n - 1; ++i) {
28                int a = direction1 * nums[i] + direction2 * nums[i + 1];
29                int absoluteDifference = Math.abs(nums[i] - nums[i + 1]);
30                maxDiff = Math.max(maxDiff, a - absoluteDifference);
31                minDiff = Math.min(minDiff, a + absoluteDifference);
32            }
33            // Update if the difference between maxDiff and minDiff improves the sum
34            maxSum = Math.max(maxSum, totalSum + Math.max(0, maxDiff - minDiff));
35        }
36        return maxSum; // Return the maximized sum after operations
37    }
38}
39
1class Solution {
2public:
3    int maxValueAfterReverse(vector<int>& nums) {
4        int totalVariation = 0; // Total variation in the original array based on sum of absolute differences
5        int maxValue = 0;       // Max value after reversing a subarray
6        int n = nums.size();
7
8        // Calculating the total initial variation of the array
9        for (int i = 0; i < n - 1; ++i) {
10            totalVariation += abs(nums[i] - nums[i + 1]);
11        }
12        maxValue = totalVariation;
13
14        // Trying to reverse from the start to each position and checking for possible improvement
15        for (int i = 0; i < n - 1; ++i) {
16            maxValue = max(maxValue, totalVariation + abs(nums[0] - nums[i + 1]) - abs(nums[i] - nums[i + 1]));
17            maxValue = max(maxValue, totalVariation + abs(nums[n - 1] - nums[i]) - abs(nums[i] - nums[i + 1]));
18        }
19
20        int directions[5] = {1, -1, -1, 1, 1}; // Direction multipliers to simplify the max/min calculations
21        const int infinity = 1 << 30;          // Placeholder for infinity to handle extreme values
22
23        // Try to find reverses that could benefit from the extremities 
24        for (int k = 0; k < 4; ++k) {
25            int dirStart = directions[k], dirEnd = directions[k + 1];
26            int maxDiff = -infinity, minSum = infinity;
27
28            // Iterate over the array and look for optimal reversing points
29            for (int i = 0; i < n - 1; ++i) {
30                int weightedEdgeValue = dirStart * nums[i] + dirEnd * nums[i + 1];
31                int currentVariation = abs(nums[i] - nums[i + 1]);
32                maxDiff = max(maxDiff, weightedEdgeValue - currentVariation);
33                minSum = min(minSum, weightedEdgeValue + currentVariation);
34            }
35
36            // Compare the differences between the max difference and min sum and update the max value accordingly
37            maxValue = max(maxValue, totalVariation + max(0, maxDiff - minSum));
38        }
39
40        return maxValue; // Return the maximum possible value after reverse operation
41    }
42};
43
1function maxValueAfterReverse(nums: number[]): number {
2    const length = nums.length;
3    let currentSum = 0;
4  
5    // Calculate the initial sum of absolute differences
6    for (let i = 0; i < length - 1; ++i) {
7        currentSum += Math.abs(nums[i] - nums[i + 1]);
8    }
9  
10    // Initialize answer with the initial sum
11    let maxSum = currentSum;
12
13    // Try reversing nums[0...i] and nums[i+1...n-1] for each i and calculate the maximum sum
14    for (let i = 0; i < length - 1; ++i) {
15        const difference = Math.abs(nums[i] - nums[i + 1]);
16        maxSum = Math.max(maxSum, currentSum + Math.abs(nums[0] - nums[i + 1]) - difference);
17        maxSum = Math.max(maxSum, currentSum + Math.abs(nums[length - 1] - nums[i]) - difference);
18    }
19  
20    // Constants for direction in the next loop, simulating a 2D direction array
21    const directions = [1, -1, -1, 1, 1];
22    const infinity = 1 << 30; // A large number representing infinity
23
24    // Try to maximize the sum by considering each subarray and its combination with directions
25    for (let k = 0; k < 4; ++k) {
26        let maxAdjustedValue = -infinity;
27        let minAdjustedValue = infinity;
28      
29        for (let i = 0; i < length - 1; ++i) {
30            const adjustedDifference = directions[k] * nums[i] + directions[k + 1] * nums[i + 1];
31            const absoluteDifference = Math.abs(nums[i] - nums[i + 1]);
32          
33            maxAdjustedValue = Math.max(maxAdjustedValue, adjustedDifference - absoluteDifference);
34            minAdjustedValue = Math.min(minAdjustedValue, adjustedDifference + absoluteDifference);
35        }
36      
37        maxSum = Math.max(maxSum, currentSum + Math.max(0, maxAdjustedValue - minAdjustedValue));
38    }
39  
40    // Return the maximum sum after reversal operation
41    return maxSum;
42}
43

Time and Space Complexity

Time Complexity

The time complexity of the function maxValueAfterReverse consists of several parts:

  • The first summation over pairwise(nums) takes O(N) time, where N is the length of the list nums. This is because we iterate over each pair of consecutive elements.
  • The second and third for loops each run O(N) times (as they iterate over each pair of pairwise(nums) once) and perform a constant amount of work within the loop.
  • The fourth for loop runs over the pairwise tuples (1, -1, -1, 1, 1) is a constant-size tuple, hence the outer loop runs a constant number of times (5 times in this case). The inner loop again runs over each pair of pairwise(nums) once, taking O(N) time. Within this inner loop, we perform a few arithmetic operations and comparisons, both of which take constant time.

Since we have a constant number of O(N) operations (the two single O(N) loops and the nested O(N) loop which is executed 5 times), we can sum these to still get O(N).

So the final time complexity of the entire function is O(N).

Space Complexity

The function uses a fixed number of single-element variables (ans, s, mx, mi), which only occupy O(1) extra space.

The pairwise generator itself does not create a list of pairs but instead produces them one at a time when iterated over, so it only uses O(1) space rather than O(N).

Thus, the overall space complexity of the function is O(1).

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄