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:
1 <= nums.length <= 3*10^4
-10^5 <= nums[i] <= 10^5
struct Solution;
impl Solution {
fn max_value_after_reverse(nums: Vec<i32>) -> i32 {
let n = nums.len();
let mut res = 0;
let mut min = std::i32::MAX;
let mut max = std::i32::MIN;
let mut total = 0;
for i in 1..n {
let a = nums[i - 1];
let b = nums[i];
total += (a - b).abs();
res = res.max((b - nums[0]).abs() - (a - b).abs());
res = res.max((a - nums[n - 1]).abs() - (a - b).abs());
min = min.min(a.max(b));
max = max.max(a.min(b));
}
total + res.max((max - min) * 2)
}
}
#[test]
fn test() {
let nums = vec![2, 3, 1, 5, 4];
let res = 10;
assert_eq!(Solution::max_value_after_reverse(nums), res);
let nums = vec![2, 4, 9, 24, 2, 1, 10];
let res = 68;
assert_eq!(Solution::max_value_after_reverse(nums), res);
}