题目描述

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

算法

(数学) $O(n) O(1)$

交换的区间中间部分在交换前后是一样的，所以我们只管边界的四个数交换前后的变化就可以了。假设四个数分别是a, b, c, d, 其中b, c 分别是选择区间的首尾

对两区间的三种情况展开讨论:
1.b, c被[a, d]/[d, a]包含

   a---------------d
        b-----c
     x     y     z   
   |____|_____|____|  

交换前: x + z
交换后: x + 2y + z
只有当4个数中较小的两个在同一端才可能有improve为2y

2.b, c与[a, d]/[d, a]相交

   a---------------d
b-----c
 x   y      z
|__|__|____________|

交换前：x + z
交换后: x + 2y + z
只有当当4个数中较小的两个在同一端才有improve为2y

3.没有相交

            a---------------d
b-----c            
   x     y          z
|_____|_____|_______________|

交换前: x + 2y + z
交换后: x + 2y + z
无论怎样都不会有improve

结论就是improve为2y，所以我们只要找出最大的y值就可以了

1.找出差值最大的|c - b|
2.特殊情况，交换的一端在边界0，n - 1

参考文献

https://leetcode.com/problems/reverse-subarray-to-maximize-array-value/discuss/489743/JavaC%2B%2BPython-One-Pass-O(1)-Space

C++ 代码

class Solution {
public:
    int maxValueAfterReverse(vector<int>& A) {
        int total = 0, res = 0, min2 = 123456, max2 = -123456, n = A.size();
        for (int i = 0; i < n - 1; ++i) {
            int a = A[i], b = A[i + 1];
            total += abs(a - b);
            // 交换的一端在0, n - 1边界，所以额外处理
            res = max(res, abs(A[0] - b) - abs(a - b));
            res = max(res, abs(A[n - 1] - a) - abs(a - b));
            // 更新最小的b，和最大的c
            min2 = min(min2, max(a, b));
            max2 = max(max2, min(a, b));
        }
        return total + max(res, (max2 - min2) * 2);
    }
};