题目描述

给你一个整数数组 nums。数组值定义为所有满足 0 <= i < nums.length-1 的 |nums[i]-nums[i+1]| 的和。

你可以选择给定数组的任意子数组，并将该子数组翻转。但你只能执行这个操作 一次。

请你找到可行的最大数组值。

样例

输入：nums = [2,3,1,5,4]
输出：10
解释：通过翻转子数组 [3,1,5]，数组变成 [2,5,1,3,4]，数组值为 10。

输入：nums = [2,4,9,24,2,1,10]
输出：68

限制

• 1 <= nums.length <= 3*10^4
• -10^5 <= nums[i] <= 10^5

算法

(数学) $O(n)$

1. 不难发现翻转一段区间，对结果造成影响的就是两个端点的变化。我们可以首先求出来当前数组的数组值，然后尝试找到翻转某个区间能达到的最大增量。
2. 考虑第一种翻转的情况，翻转的区间有一个端点是整个数组的端点。此时，可以通过两次线性扫描求出这种情况下的最大增量。
3. 第二种情况，翻转的区间的两个端点都不是整个数组的端点。假设待翻转的区间左右端点的值分别为 b 和 c，且左端点上一个数字的值为 a，右端点下一个数字的值为 d。如果区间 [min(a, b), max(a, b)] 与 [min(c, d), max(c, d)] 不相交，则交换 b 和 c 的值能带来增量。用数学的公式表示就是 |a-b| + |c-d| < |a-c| + |b-d| 当且仅当这两个区间不相交。假设 min(c, d) > max(a, b)，则交换所带来的增量为 2 * min(c, d) - max(a, b)。
4. 通过两次线性扫描来求解第二种情况的最大增量。第一次线性扫描从头开始，求解 min(c, d) > max(a, b) 的情况。枚举 c，同时维护最小的 b 值。第二次线性扫描从末尾开始，求解 min(a, b) > max(c, d) 的情况。枚举 b，同时维护最小的 c 值。

时间复杂度

• 若干次线性扫描，时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int maxValueAfterReverse(vector<int>& nums) {
        int n = nums.size();
        int tot = 0, res = 0;
        for (int i = 0; i < n - 1; i++)
            tot += abs(nums[i] - nums[i + 1]);

        for (int i = 1; i < n; i++)
            res = max(res, abs(nums[0] - nums[i]) - abs(nums[i - 1] - nums[i]));

        for (int i = 0; i < n - 1; i++)
            res = max(res, abs(nums[n - 1] - nums[i]) - abs(nums[i + 1] - nums[i]));

        if (n <= 3)
            return tot + res;

        int x;
        x = max(nums[0], nums[1]);

        for (int i = 2; i < n - 1; i++) {
            int m = min(nums[i], nums[i + 1]);
            if (m > x)
                res = max(res, 2 * (m - x));
            x = min(x, max(nums[i - 1], nums[i]));
        }

        x = max(nums[n - 1], nums[n - 2]);

        for (int i = n - 3; i >= 1; i--) {
            int m = min(nums[i], nums[i - 1]);
            if (m > x)
                res = max(res, 2 * (m - x));
            x = min(x, max(nums[i], nums[i + 1]));
        }

        return tot + res;
    }
};