Leetcode 1330. Reverse Subarray To Maximize Array Value
Problem Explanation
Given an array of integers, the object of this problem is to find the maximum possible value of the array after reversing a subarray once. The value of the array is defined as the sum of the absolute difference between each element and its immediate succeeding element.
Let's illustrate this problem with an example.
If we are given nums = [2,3,1,5,4]
, by reversing the subarray [3,1,5]
, our array becomes [2,5,1,3,4]
. This array gives the maximum possible value, which is 10 (3 + 4 + 2 + 1)
.
The chosen reversing subarray can be of any size including the entire array itself. If reversing the subarray doesn't provide any improvements to the array's value, the original array is considered as the result array.
Solution Approach
The approach involves several steps:
- We first compute the initial sum of absolute differences
total
of the given array. - Then, we find two elements in the array such that they maximize the difference of the new array value and
total
when reversing the subarray. We usemin
andmax
to track the minimum maximum and maximum minimum values. - We find the maximal improvement
diff
for all pairs of elements in the array. - The result is
total + diff
.
C++ Solution
1
2cpp
3class Solution {
4 public:
5 int maxValueAfterReverse(vector<int>& nums) {
6 int total = 0;
7 int min = INT_MAX;
8 int max = INT_MIN;
9
10 for (int i = 0; i + 1 < nums.size(); ++i) {
11 int a = nums[i];
12 int b = nums[i + 1];
13 total += abs(a - b);
14 min = std::min(min, std::max(a, b));
15 max = std::max(max, std::min(a, b));
16 }
17
18 int diff = std::max(0, (max - min) * 2);
19
20 for (int i = 0; i + 1 < nums.size(); ++i) {
21 int a = nums[i];
22 int b = nums[i + 1];
23 diff = std::max(diff, abs(nums[0] - b) - abs(a - b));
24 diff = std::max(diff, abs(nums.back() - a) - abs(a - b));
25 }
26
27 return total + diff;
28 }
29};
In the C++ solution above, we first loop through the array to calculate the total value and find the min
and max
values. We then iterate through the array a second time to calculate diff
.# Python Solution
1 2python 3class Solution: 4 def maxValueAfterReverse(self, nums): 5 total, n = 0, len(nums) 6 7 min_max, max_min = float('inf'), float('-inf') 8 9 for i in range(n-1): 10 a, b = sorted([nums[i], nums[i+1]]) 11 total += abs(a - b) 12 min_max = min(min_max, max(nums[i], nums[i+1])) 13 max_min = max(max_min, min(nums[i], nums[i+1])) 14 15 diff = max(0, (max_min - min_max) * 2) 16 17 for i in range(n-1): 18 diff = max(diff, abs(nums[0] - nums[i+1]) - abs(nums[i] - nums[i+1])) 19 diff = max(diff, abs(nums[-1] - nums[i]) - abs(nums[i] - nums[i+1])) 20 21 return total + diff
In the Python solution, we replace C++'s INT_MAX
and INT_MIN
with Python's float('inf')
and float('-inf')
respectively.
JavaScript Solution
1 2javascript 3function maxValueAfterReverse(nums) { 4 let total = 0; 5 let min_max = Number.MAX_SAFE_INTEGER; 6 let max_min = Number.MIN_SAFE_INTEGER; 7 8 for(let i = 0 ; i + 1 < nums.length ; ++i) { 9 let a = nums[i]; 10 let b = nums[i + 1]; 11 total += Math.abs(a - b); 12 min_max = Math.min(min_max, Math.max(a, b)); 13 max_min = Math.max(max_min, Math.min(a, b)); 14 } 15 16 let diff = Math.max(0, (max_min - min_max) * 2); 17 18 for(let i = 0 ; i + 1 < nums.length ; ++i) { 19 let a = nums[i]; 20 let b = nums[i + 1]; 21 diff = Math.max(diff, Math.abs(nums[0] - b) - Math.abs(a - b)); 22 diff = Math.max(diff, Math.abs(nums[nums.length-1] - a) - Math.abs(a - b)); 23 } 24 25 return total + diff; 26}
In JavaScript, we replace C++'s INT_MAX
and INT_MIN
with JavaScript's Number.MAX_SAFE_INTEGER
and Number.MIN_SAFE_INTEGER
respectively.
Java Solution
1 2java 3class Solution { 4 public int maxValueAfterReverse(int[] nums) { 5 int total = 0; 6 int min_max = Integer.MAX_VALUE; 7 int max_min = Integer.MIN_VALUE; 8 9 for(int i = 0; i + 1 < nums.length; i++) { 10 int a = nums[i]; 11 int b = nums[i + 1]; 12 total += Math.abs(a - b); 13 min_max = Math.min(min_max, Math.max(a, b)); 14 max_min = Math.max(max_min, Math.min(a, b)); 15 } 16 17 int diff = Math.max(0, (max_min - min_max) * 2); 18 19 for(int i = 0 ; i + 1 < nums.length; i++) { 20 int a = nums[i]; 21 int b = nums[i + 1]; 22 diff = Math.max(diff, Math.abs(nums[0] - b) - Math.abs(a - b)); 23 diff = Math.max(diff, Math.abs(nums[nums.length-1] - a) - Math.abs(a - b)); 24 } 25 26 return total + diff; 27 } 28}
The Java solution uses a similar strategy as the C++ and Python versions but the syntax is different. For example, Java uses Math.max
and Math.min
functions to calculate the minimum and maximum values. In Java, arrays are also zero-indexed, so the element at the end of the array is accessed with nums[nums.length - 1]
.
Got a question?ย Ask the Teaching 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.