翻转子数组得到最大的数组值

题目

1330. 翻转子数组得到最大的数组值

---

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

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

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

示例 1：

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

示例 2：

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

提示：

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

题解

方法一：

思路

对于选取的反转区间是原数组的一个前缀或后缀可以花$O(n)$求出交换后的最大值。

设$p = \sum \limits_{i=1}^{n-1} |nums[i]-nums[i-1]|$，也就是在交换之前的数组值。

不妨设现在交换的是$[0,i]$，那么交换后的数组值将变为$p-|nums[i+1]-nums[i]|+|nums[i+1]-nums[0]|$

因此可以预处理前缀和后缀
$\max \limits_{i=1}^{n-1} (p-|nums[i]-nums[i-1]|+|nums[i]-nums[0]|)$，$\max \limits_{i=0}^{n-2} (p-|nums[i]-nums[i+1]|+|nums[n-1]-nums[i]|)$作为候选答案

对于反转区间在为$[i,j],i>0, j<n-1 $

我们设$a = nums[i-1], b = nums[i], c = nums[j], d = nums[j+1]$

这时交换后的数组值变化量为：
$\Delta = |a-c|+|b-d|-|a-b|-|c-d|$

根据abcd的大小关系去掉绝对值有24种情况。

剩余情况可以枚举最小的两个数，再根据以下恒等式进行变化。
枚举最小的两个数有$C_{4}^{2}=6$种情况，由于对称性可以去除一半的情况。

|x - y| = max(x, y) - min(x, y)
x + y = max(x, y) + min(x, y)
x + y + |x - y| = 2 * max(x, y)
x + y - |x - y| = 2 * min(x, y)

当最小的两个数是a和b时，即$max(a,b)\le min(c,d)$。

$\begin{array}{lll}
\Delta & = & |a-c|+|b-d|-|a-b|-|c-d| \
& = & c-a+d-b-|a-b|-|c-d| \
& = & c+d-|c-d| - (a+b+|a-b|) \
& = & 2min(c,d)-2max(a,b) \ge 0 \
\end{array}$

由对称性，可以化简最小的两个数是c和d，即$max(c,d)\le min(a,b)$。

这两种情况可以让数组值增大。

当最小的两个数是a和c时，即$max(a,c)\le min(b,d)$。

$\begin{array}{lll}
\Delta & = & |a-c|+|b-d|-|a-b|-|c-d| \
& = & |a-c|+|b-d|-(b-a)-(d-c) \
& = & 2max(a,c)-2min(b,d) \le 0 \
\end{array}$

由对称性，可以化简最小的两个数是b和d，即$max(a,c)\le min(b,d)$。

这两种情况会让数组值减小。

当最小的两个数是a和d时，即$max(a,d)\le min(b,c)$。

$\begin{array}{lll}
\Delta & = & |a-c|+|b-d|-|a-b|-|c-d| \
& = & c-a+d-b-(b-a)-(c-d) \
& = & 0 \
\end{array}$

由对称性，可以化简最小的两个数是b和c，即$max(b,c)\le min(a,d)$。

这两种情况不会让数组值变化。

综上，只需要考虑$max(a,b)\le min(c,d)$和$max(c,d)\le min(a,b)$。

我们设计求出$max(a,b)\le min(c,d)$这种情况的算法。再由于对称性，然后将数组反转，用相同的算法再求一次即可得到$max(c,d)\le min(a,b)$的答案。

我们维护一个前缀$[1,i]$中$max(nums[i-1], nums[i])$的最小值，记为$m_i$。然后对于交换区间是以i为右端点的最优值为$max(nums[i-1], nums[i])-m_{i-1}$

代码

class Solution {
public:
    using ll = long long;
    int maxValueAfterReverse(vector<int>& nums) {
        int n = nums.size();
        if (n==1) return 0;
        int p = 0;
        for (int i=1; i<n; i++) p += abs(nums[i]-nums[i-1]);
        // cout << p << "\n";
        int ans = p;
        for (int i=1; i<n; i++) ans = max(ans, p+abs(nums[i]-nums[0])-abs(nums[i]-nums[i-1]));
        for (int i=0; i<n-1; i++) ans = max(ans, p+abs(nums[n-1]-nums[i])-abs(nums[i]-nums[i+1]));
        // cout << ans << "\n";
        auto fun = [&]() {
            int mn = max(nums[0], nums[1]);
            for (int i=2; i<n; i++) {
                ans = max(ans, p+2*(min(nums[i-1], nums[i])-mn));
                mn = min(mn, max(nums[i-1], nums[i]));
            }
        };
        fun();
        reverse(nums.begin(), nums.end());
        fun();
        return ans;
    }
};