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 1: Classification Discussion + Enumeration
According to the problem description, we need to find the maximum value of the array $\sum_{i=0}^{n-2} |a_i - a_{i+1}|$ when reversing a subarray once.
Next, we discuss the following cases:
- Do not reverse the subarray.
- Reverse the subarray, and the subarray "includes" the first element.
- Reverse the subarray, and the subarray "includes" the last element.
- Reverse the subarray, and the subarray "does not include" the first and last elements.
Let $s$ be the array value when the subarray is not reversed, then $s = \sum_{i=0}^{n-2} |a_i - a_{i+1}|$. We can initialize the answer $ans$ to $s$.
If we reverse the subarray and the subarray includes the first element, we can enumerate the last element $a_i$ of the reversed subarray, where $0 \leq i < n-1$. In this case, $ans = \max(ans, s + |a_0 - a_{i+1}| - |a_i - a_{i+1}|)$.
Similarly, if we reverse the subarray and the subarray includes the last element, we can enumerate the first element $a_{i+1}$ of the reversed subarray, where $0 \leq i < n-1$. In this case, $ans = \max(ans, s + |a_{n-1} - a_i| - |a_i - a_{i+1}|)$.
If we reverse the subarray and the subarray does not include the first and last elements, we consider any two adjacent elements in the array as a point pair $(x, y)$. Let the first element of the reversed subarray be $y_1$, and its left adjacent element be $x_1$; let the last element of the reversed subarray be $x_2$, and its right adjacent element be $y_2$.
At this time, compared to not reversing the subarray, the change in the array value is $|x_1 - x_2| + |y_1 - y_2| - |x_1 - y_1| - |x_2 - y_2|$, where the first two terms can be expressed as:
$$ \left | x_1 - x_2 \right | + \left | y_1 - y_2 \right | = \max \begin{cases} (x_1 + y_1) - (x_2 + y_2) \ (x_1 - y_1) - (x_2 - y_2) \ (-x_1 + y_1) - (-x_2 + y_2) \ (-x_1 - y_1) - (-x_2 - y_2) \end{cases} $$
Then the change in the array value is:
$$ \left | x_1 - x_2 \right | + \left | y_1 - y_2 \right | - \left | x_1 - y_1 \right | - \left | x_2 - y_2 \right | = \max \begin{cases} (x_1 + y_1) - \left |x_1 - y_1 \right | - \left ( (x_2 + y_2) + \left |x_2 - y_2 \right | \right ) \ (x_1 - y_1) - \left |x_1 - y_1 \right | - \left ( (x_2 - y_2) + \left |x_2 - y_2 \right | \right ) \ (-x_1 + y_1) - \left |x_1 - y_1 \right | - \left ( (-x_2 + y_2) + \left |x_2 - y_2 \right | \right ) \ (-x_1 - y_1) - \left |x_1 - y_1 \right | - \left ( (-x_2 - y_2) + \left |x_2 - y_2 \right | \right ) \end{cases} $$
Therefore, we only need to find the maximum value $mx$ of $k_1 \times x + k_2 \times y$, where $k_1, k_2 \in {-1, 1}$, and the corresponding minimum value $mi$ of $|x - y|$. Then the maximum change in the array value is $mx - mi$. The answer is $ans = \max(ans, s + \max(0, mx - mi))$.
In the code implementation, we define an array of length 5, $dirs=[1, -1, -1, 1, 1]$. Each time we take two adjacent elements of the array as the values of $k_1$ and $k_2$, which can cover all cases of $k_1, k_2 \in {-1, 1}$.
The time complexity is $O(n)$, where $n$ is the length of the array $nums$. The space complexity is $O(1)$.
Similar problems:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
|