We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Reverse Subarray To Maximize Array Value

Number: 1255

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given an integer array nums, the "value" of the array is defined as the sum of |nums[i] - nums[i+1]| for all 0 <= i < nums.length - 1. You are allowed to reverse exactly one subarray (continuous segment) of nums. The task is to find the maximum possible value of the array after applying at most one such reversal.

Key Insights

  • The initial value (baseline) is the sum of absolute differences between consecutive elements.
  • Reversing a subarray only changes the differences at the boundaries (the elements just before and after the reversed portion).
  • Two main reversal strategies: • Reversals that include either the first or the last element. • Reversals that are entirely internal which might “adjust” differences in a way that increases the overall sum.
  • For the reversals touching the boundaries, evaluate the impact by trying to replace an edge difference with a new difference involving the extreme element (first or last).
  • For internal reversals, iterate over every adjacent pair and track two values: • The minimum of max(nums[i], nums[i+1]) seen so far. • The maximum of min(nums[i], nums[i+1]) seen so far. Using these, one can derive a candidate improvement of 2 * (max_candidate − min_candidate).
  • Finally, add the best improvement (if any) to the baseline sum.

Space and Time Complexity

Time Complexity: O(n) – we traverse the array a few times. Space Complexity: O(1) – only constant extra space is used.

Solution

To solve the problem, first calculate the baseline sum value as the sum of absolute differences between each pair of consecutive elements. Next, check the improvement from reversing a subarray that touches an endpoint. For every adjacent pair (i, i+1), consider:

  1. If we reverse a subarray that starts at index 0 and ends at i, the difference at i (or at the boundary connecting to i+1) might become |nums[i+1] – nums[0]|.
  2. Similarly, if we reverse a subarray starting at i+1 and ending at the last index, the difference at i might become |nums[n-1] – nums[i]|. Compute these candidates to update the maximum gain. Then, for subarrays fully inside, note that elements in the middle maintain their internal differences but only the boundaries change. For every consecutive pair in the array, keep track of two values:
  • low_candidate: the minimum of max(nums[i], nums[i+1])
  • high_candidate: the maximum of min(nums[i], nums[i+1]) The maximum extra gain possible from an internal reversal is 2 * (high_candidate − low_candidate), because reversing can “flip” the sign of the difference and possibly add this gap twice. Finally, the answer is the baseline sum plus the maximum improvement found.

Code Solutions

# Python solution for Reverse Subarray To Maximize Array Value

def maxValueAfterReverse(nums):
    # Compute the baseline sum: sum of absolute differences between consecutive elements.
    n = len(nums)
    base_value = 0
    for i in range(n - 1):
        base_value += abs(nums[i] - nums[i+1])
    
    # Initialize result with the baseline. Also initialize candidate for internal reversal.
    best_gain = 0
    
    # Consider reversing subarray that includes the first element or the last element.
    # For every adjacent pair, consider if reversing prefix or suffix gives benefit.
    for i in range(1, n):
        # Reversal affecting the beginning:
        gain = abs(nums[i] - nums[0]) - abs(nums[i] - nums[i-1])
        if gain > best_gain:
            best_gain = gain
        
        # Reversal affecting the end:
        gain = abs(nums[-1] - nums[i-1]) - abs(nums[i] - nums[i-1])
        if gain > best_gain:
            best_gain = gain
    
    # For internal reversal (that does not touch the boundaries), the best improvement
    # is determined by 2 * (max(min(nums[i], nums[i+1])) - min(max(nums[i], nums[i+1])))
    min_of_max = float('inf')   # minimum of max(nums[i], nums[i+1])
    max_of_min = float('-inf')  # maximum of min(nums[i], nums[i+1])
    
    for i in range(n - 1):
        a = nums[i]
        b = nums[i+1]
        # For each pair update the tracking values.
        min_of_max = min(min_of_max, max(a, b))
        max_of_min = max(max_of_min, min(a, b))
    
    # The maximal possible improvement by reversing an internal subarray.
    internal_gain = 2 * (max_of_min - min_of_max)
    if internal_gain > best_gain:
        best_gain = internal_gain

    # Return the maximum possible value.
    return base_value + best_gain

# Example usage:
if __name__ == '__main__':
    test_nums = [2,3,1,5,4]
    print("Maximum array value:", maxValueAfterReverse(test_nums))  # Expected output: 10
← Back to All Questions