首页算法

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

# 数学

对于 ⋯ab⋯xy...→翻转后⋯ax⋯by⋯\cdots ab \cdots xy... \stackrel{翻转后}{\rightarrow} \cdots ax \cdots by\cdots

  • 可以发现，只会影响两边的值，而不会影响局部的值

可以得出：d=(∣x−a∣+∣y−b∣)−∣b−a∣−∣y−x∣①d =(|x-a| + |y - b|) - |b-a|-|y-x| \quad ①

  • 只需要求出 dd 的最大值即可。

可以暴力枚举 a,xa,x 求出最大值，但是需要 O(n2)O(n^2) 的时间复杂度，如何优化呢？

class Solution {
 public int maxValueAfterReverse(int[] nums) {
     int n = nums.length;
     int origin = 0;
     for (int i = 1; i < n; i++) {
         origin += Math.abs(nums[i] - nums[i - 1]);
     }
     int ans = origin;
     for (int i = 0; i < n; i++) {
         int r = i == n - 1 ? 0 : Math.abs(nums[i + 1] - nums[i]);
         for (int j = 0; j < i; j++) {
             int l = j == 0 ? 0 : Math.abs(nums[j] - nums[j - 1]);
             //swap
             int cl = j == 0 ? 0 : Math.abs(nums[i] - nums[j - 1]);
             int cr = i == n - 1 ? 0 : Math.abs(nums[i + 1] - nums[j]);
             ans = Math.max(ans, origin - (r + l) + (cl + cr));
         }
     }
     return ans;
 }
}

参考：简单、暴力、不需要分类讨论的数学分析

绝对值与最大值的关系：∣a∣=max(a,−a)|a| = max(a,-a)

加法对最大值的分配率：max(a,b)+c=max(a+c,b+c)max(a,b)+c = max(a+c,b+c)

$d =(|x-a| + |y - b|) - |b-a|-|y-x| $

=max(x−a,a−x)+max(y−b,b−y)−∣b−a∣−∣y−x∣=max(x-a,a-x)+max(y-b,b-y)-|b-a|-|y-x|

=max{x−a+max(y−b,b−y)a−x+max(y−b,b−y)}−∣b−a∣−∣y−x∣=max\left\{ \begin{matrix} x-a+max(y-b,b-y)\\ a-x+max(y-b,b-y)\end{matrix} \right\}-|b-a|-|y-x|

=max{y−b+x−ab−y+x−ay−b+a−xb−y+a−x}−∣b−a∣−∣y−x∣=max\left\{ \begin{matrix} y-b+x-a\\b-y+x-a\\ y-b+a-x\\b-y+a-x\end{matrix} \right\}-|b-a|-|y-x|\\

=max{y+x−∣y−x∣−b−a−∣b−a∣−y+x−∣y−x∣+b−a−∣b−a∣y−x−∣y−x∣−b+a−∣b−a∣−y−x−∣y−x∣+a+b−∣b−a∣}=max\left\{ \begin{matrix} y+x-|y-x|\quad-b-a-|b-a|\\-y+x-|y-x|\quad+b-a-|b-a|\\y-x-|y-x|\quad-b+a-|b-a|\\-y-x-|y-x|\quad+a+b-|b-a|\end{matrix} \right\}

求解： x+yx+y 的最大值，我们可以在枚举 xx 的过程中并保存 yy 的最大值即可

注意：还需要单独考虑边界

class Solution {
    public int maxValueAfterReverse(int[] nums) {
        int n = nums.length;
        int mx1 = Integer.MIN_VALUE / 2, mx2 = Integer.MIN_VALUE / 2, mx3 = Integer.MIN_VALUE / 2, mx4 = Integer.MIN_VALUE / 2;
        int ans = 0;
        int ds = 0;
        // 边界
        for (int i = 0; i < n - 1; i++) {
            int y = nums[i + 1], x = nums[i];
            int dxy = Math.abs(x - y);
            ds += dxy;
            // 左边界
            ans = Math.max(ans, Math.abs(nums[0] - y) - dxy);
            // 右边界
            ans = Math.max(ans, Math.abs(nums[n - 1] - x) - dxy);
            // 中间 4 种情况
            ans = Math.max(ans,
                    Math.max(
                            Math.max(y + x + mx1, -y + x + mx2),
                            Math.max(y - x + mx3, -y - x + mx4)
                    ) - dxy);
            mx1 = Math.max(mx1, -y - x - dxy);
            mx2 = Math.max(mx2, y - x - dxy);
            mx3 = Math.max(mx3, -y + x - dxy);
            mx4 = Math.max(mx4, y + x - dxy);
        }
        return ans + ds;
    }
}
# 数学 + 分类讨论




参考：不会化简？请看这


(1)	 ∣a−b∣=max(a,b)−min(a,b)|a-b|= max(a,b)-min(a,b)


(2)	a+b=max(a,b)+min(a,b)a + b =max(a,b)+min(a, b)


(3)	a+b+∣a−b∣=(2)+(1)=2⋅ max(a,b)a+b+|a-b|=(2)+(1)=2\cdot\,max(a,b)


(4)	a+b−∣a−b∣=(2)−(1)=2⋅ min(a,b)a+b-|a-b|=(2)-(1)=2\cdot\,min(a,b)




$d =(|x-a| + |y - b|) - |b-a|-|y-x| $


对于 a,b,x,ya,b,x,y 之间大小关系一共有 4!4!，共 2424 种情况。


可以从这 44 个数选出任意 22 个数作为最小值，一共有 $C_4^2 = 6 $  种情况




由于对称性，可以分类讨论 33 种情况。




① max(a,b)<=min(x,y)max(a,b)<=min(x,y)


    

  • 

    d=x−a+y−b−∣b−a∣−∣y−x∣d=x-a+y-b-|b-a|-|y-x|
    

    =−(a+b+∣a−b∣)+x+y−∣y−x∣=-(a+b+|a-b|)+x+y-|y-x|
    

    =−2⋅ max(a,b)+2⋅ min(x,y)=-2\cdot\,max(a,b) + 2\cdot\,min(x,y)
    

    ≥0\ge0
    

    • 

  • 

    由对称性， max(x,y)<=min(a,b)max(x,y)<=min(a,b)
    

      

    • d=−2⋅ max(x,y)+2⋅ min(a,b)≥0d=-2\cdot\,max(x,y) + 2\cdot\,min(a,b) \ge0
      • 

    

    • 



② max(a,x)<=min(b,y)max(a,x)<=min(b,y)


    

  • 

    d=∣x−a∣+∣y−b∣−b+a−y+xd=|x-a|+|y-b|-b+a-y+x
    

    =x+a+∣x−a∣−(b+y−∣y−b∣)=x+a+|x-a|-(b+y-|y-b|)
    

    =2⋅ max(x,a)−2⋅ min(b,y)=2\cdot\,max(x,a)-2\cdot\,min(b,y)
    

    <=0<=0
    

    • 

  • 

    由对称性， max(b,y)<=min(a,x)max(b,y)<=min(a,x)
    

      

    • d=2⋅ max(b,y)−2⋅ min(a,x)≤0d=2\cdot\,max(b,y)-2\cdot\,min(a,x)\le0
      • 

    

    • 



当 d=0d=0 时，⋯ab⋯xy...→翻转后⋯ax⋯by⋯\cdots ab \cdots xy... \stackrel{翻转后}{\rightarrow} \cdots ax \cdots by\cdots，只翻转一个子数组的情况。




可以不用考虑




② max(a,y)<=min(b,x)max(a,y)<=min(b,x)


    

  • 

    d=x−a+b−y−b+a−x+yd=x-a+b-y-b+a-x+y
    

    =0=0
    

    • 

  • 

    由对称性， max(a,y)<=min(b,x)max(a,y)<=min(b,x)
    

      

    • d=0d=0
      • 

    

    • 



从上述可以得出，只有情况 ① d>=0d>=0 才会使得数组值增大。


即：d=2⋅ min(x,y)−2⋅ max(a,b)d=2\cdot\,min(x,y)-2\cdot\,max(a,b)


class Solution {
    public int maxValueAfterReverse(int[] nums) {
        int n = nums.length;
        int mx = Integer.MIN_VALUE, mn = Integer.MAX_VALUE;
        int ans = 0;
        int ds = 0;
        // 边界
        for (int i = 0; i < n - 1; i++) {
            int y = nums[i + 1], x = nums[i];
            int dxy = Math.abs(x - y);
            ds += dxy;
            // 左边界
            ans = Math.max(ans, Math.abs(nums[0] - y) - dxy);
            // 右边界
            ans = Math.max(ans, Math.abs(nums[n - 1] - x) - dxy);
            // 维护 min (x, y) 的最大值 mx
            mx = Math.max(mx, Math.min(x, y));
            // 维护 max (a, b) 的最小值 mn
            mn = Math.min(mn, Math.max(x, y));
        }
        return Math.max(ans, 2 * (mx - mn)) + ds;
    }
}