Reverse Subarray To Maximize Array Value 翻转子数组得到最大的数组值

问题描述：

问题

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

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

请你找到可行的最大【数组值】 。
nums.length的范围[1,30000], nums[i]范围[-100000,100000]

分析

对于 一个整数数组 a b c d e f g,原始数组的 value，就是abs(a-b)+abs(b-c)+abs(c-d)+abs(d-e)+abs(e-f)+abs(f-g).
如果将b~f反转，原数组就是 a f e d c b g,该数组的value就是
abs(a-f)+abs(f-e)+abs(e-d)+abs(d-c)+abs(c-b)+abs(b-g).
这2个value都有公共相同的部分abs(b-c)+abs(c-d)+abs(d-e)+abs(e-f)，所以一旦反转，从i~j进行反转，那么不同的就是
abs(nums[i-1]-nums[j]),abs(nums[i]-nums[j+1]),
原始数组的value，记value1=abs(nums[0]-nums[1])+ abs(nums[i-1]-nums[i])+abs(nums[i]-nums[i+1])+…+abs(nums[j-1]-nums[j])+…+abs(nums[n-2]-nums[n-1])
反转后的记为value2 = abs(nums[0]-nums[1])+ abs(nums[i-1]-nums[j])+abs(nums[j]-nums[j-1])+…+abs(nums[i]-nums[j+1])+…+abs(nums[n-2]-nums[n-1])
value2 =value1 -(abs(nums[i-1]-nums[i])+abs(nums[j]-nums[j+1]))
+abs(nums[i-1]-nums[j])+abs(nums[i]-nums[j+1])
如果反转的长度 = n，或者长度 = 1，那么value2= value1.
否则v2与v1的关系就取决于4个元素分别是nums[i-1],nums[i],nums[j],nums[j+1],即发生交换的位置，可以使用a,b,x,y进行对应。
原始的v1是定值，不会改变，在不同位置发生交换产生的v2
v2=v1-(abs(a-b)+abs(x-y))+ abs(a-x)+abs(b-y)
v2和v1的关系就取决于后面一段，ABS=abs(a-x)+abs(b-y)-(abs(a-b)+abs(x-y))的大小。
如果可以确定ABS的范围，就可以得到V2的范围，最大值就可以知道了。
分类讨论ax,ab的关系，by，xy的关系。即abxy的排列,最多需要判断24种情况。
当然，如果走暴力枚举ij的位置，时间复杂度就是ONN。但是以上面的规模，TLE是必然的。所以只能走其他的方式。
对于abs(a-b)来说，去掉abs，就必须判断ab的关系。
a>=b,=> a-b.如果是a<b,则是b-a.
=abs(a-b) = max(a,b)-min(a,b);
同样 a+b = max(a,b)+ min(a,b)
所以可以得到
a+b+abs(a-b)= 2max(a,b)
a+b-abs(a-b)= 2min(a,b)
如果可以确定2个最小的 ，那么剩余2个就是较大的。以这个角度思考abxy的关系。
a,b <= x,y
ABS=abs(a-x)+abs(b-y)-(abs(a-b)+abs(x-y))
= > x-a+y-b -abs(a-b)-abs(x-y)
= > x+y-abs(x-y)-(a+b+abs(a-b))
= > 2min(x,y)- 2max(a,b) >=0
如果 a,b>=x,y ，ABS= 2min(a,b)- 2max(x,y)>=0 ,与上面是一个值，其实是对称性，所以这个大类下，有4种排列，ab2种，xy2种。
另一种 a,x <= b,y ,
ABS=abs(a-x)+abs(b-y)-(abs(a-b)+abs(x-y))
= >abs(a-x)+abs(b-y)-(b-a)-(y-x)
= >abs(a-x)+abs(b-y)-b+a-y+x
= >abs(a-x)+abs(b-y)-(b+y)+(a+x)
= >2max(a,x)-2min(b,y)<=0

另一种 a,y <= b,x ,
ABS=abs(a-x)+abs(b-y)-(abs(a-b)+abs(x-y))
= >(x-a)+(b-y)-(b-a)-(x-y)
= 0
只有在第一种场景下a,b <= x,y,2min(x,y)- 2max(a,b)会影响到最大值。
也就是说，ABS的最大值，一定会出现在当ab相邻且最大值尽可能小，xy相邻且最小值尽可能大。
这样一次遍历时间复杂度ON，空间O1 。

时间复杂度 O(N)
空间复杂度： O(1)

代码

class Solution {
    public int maxValueAfterReverse(int[] nums) {
        int value = 0, n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            value += Math.abs(nums[i] - nums[i + 1]);
        }
        int mx1 = 0;
        for (int i = 1; i < n - 1; i++) {
            mx1 = Math.max(mx1, Math.abs(nums[0] - nums[i + 1]) - Math.abs(nums[i] - nums[i + 1]));
            mx1 = Math.max(mx1, Math.abs(nums[n - 1] - nums[i - 1]) - Math.abs(nums[i] - nums[i - 1]));
        }
        int mx2 = Integer.MIN_VALUE, mn2 = Integer.MAX_VALUE;
        for (int i = 0; i < n - 1; i++) {
            int x = nums[i], y = nums[i + 1];
            mx2 = Math.max(mx2, Math.min(x, y));
            mn2 = Math.min(mn2, Math.max(x, y));
        }
        return value + Math.max(mx1, 2 * (mx2 - mn2));
    }
} 

代码来源于官解

class Solution {
    public int maxValueAfterReverse(int[] nums) {
        int base = 0, d = 0, n = nums.length;
        int mx = Integer.MIN_VALUE, mn = Integer.MAX_VALUE;
        for (int i = 1; i < n; i++) {
            int a = nums[i - 1], b = nums[i];
            int dab = Math.abs(a - b);
            base += dab;
            mx = Math.max(mx, Math.min(a, b));
            mn = Math.min(mn, Math.max(a, b));
            d = Math.max(d, Math.max(Math.abs(nums[0] - b) - dab, // i=0
                                     Math.abs(nums[n - 1] - a) - dab)); // j=n-1
        }
        return base + Math.max(d, 2 * (mx - mn));
    }
} 

代码来源于灵神大佬，比较简洁

Tag

Array Math