1330. Reverse Subarray To Maximize Array Value

Description

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.

 

Solutions

Solution: Greedy

• Time complexity: O(n)
• Space complexity: O(1)

 

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
const maxValueAfterReverse = function (nums) {
  const n = nums.length;
  let minMax = Number.MAX_SAFE_INTEGER;
  let maxMin = Number.MIN_SAFE_INTEGER;
  let total = 0;

  for (let index = 1; index < n; index++) {
    const a = nums[index - 1];
    const b = nums[index];

    total += Math.abs(a - b);
    minMax = Math.min(minMax, Math.max(a, b));
    maxMin = Math.max(maxMin, Math.min(a, b));
  }
  let maxDiff = (maxMin - minMax) * 2;

  for (let index = 1; index < n; index++) {
    const a = nums[index - 1];
    const b = nums[index];
    const diff = Math.abs(a - b);
    const headDiff = Math.abs(nums[0] - b) - diff;
    const tailDiff = Math.abs(nums[n - 1] - a) - diff;

    maxDiff = Math.max(maxDiff, headDiff, tailDiff);
  }
  return total + maxDiff;
};