题目

给你一个整数数组 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

提示：

• 2 <= nums.length <= 3*10⁴
• -10⁵ <= nums[i] <= 10⁵
• 答案保证在 32 位整数范围内。

思路

暴力解法

解法

class Solution {
    public int maxValueAfterReverse(int[] nums) {
        //先考虑的暴力解法。
        //i与j的子数组翻转，只有两项值发生了变化
        //……nums[i-1] nums[i]…… nums[j] nums[j+1]…… 
        //变的是abs(nums[i-1]-nums[i])+abs(nums[j]-nums[j+1])
        //变成了abs(nums[i-1]-nums[j])+abs(nums[i]-nums[j+1])
        //只翻转一次，相当于在初始数组的基础上，仅仅改变了上面两项
        int count=0;
        for(int i=0;i<nums.length-1;i++){
            count+=Math.abs(nums[i]-nums[i+1]);
        }
        int chushi=count;
        /*超时，看来o(n^2)不行，那就换个思路
        for(int i=0;i<nums.length-1;i++){
            for(int j=i+1;j<nums.length;j++){
                if(i==0&&j==nums.length-1)continue;
                else if(i==0&&j!=nums.length-1){
                    count=Math.max(count,chushi-Math.abs(nums[j]-nums[j+1])+Math.abs(nums[i]-nums[j+1]));
                }
                else if(j==nums.length-1&&i!=0){
                    count=Math.max(count,chushi-Math.abs(nums[i-1]-nums[i])+Math.abs(nums[i-1]-nums[j]));
                }
                else{
                    count=Math.max(count,chushi-Math.abs(nums[i-1]-nums[i])-Math.abs(nums[j]-nums[j+1])
                                              +Math.abs(nums[i-1]-nums[j])+Math.abs(nums[i]-nums[j+1]));
                }
            }
        }*/
        //绝对值的定义其实是数轴上两个点距离，
        //从abs(nums[i-1]-nums[i])+abs(nums[j]-nums[j+1])到abs(nums[i-1]-nums[j])+abs(nums[i]-nums[j+1])转化为距离
        //假设四个点为abcd,之前为(a,b)(c,d)
        //其中a=min(nums[i],nums[i-1]),b=max(nums[i],nums[i-1]),cd类似
        //之后可能变成(a,d)(b,c)或者(a,c)(b,d)
        //[1]如果之前的两个区间没有交集,不管是(a,d)(b,c)还是(a,c)(b,d),距离的增加量&=2*(区间距离差)
        //[2]如果之前的两个区间有交集,距离的变化不会增加:可能不变,可能减少。画个数轴图很清晰。
        for(int i=0;i<nums.length-1;i++){
            count=Math.max(count,chushi-Math.abs(nums[i]-nums[i+1])+Math.abs(nums[0]-nums[i+1]));
            count=Math.max(count,chushi-Math.abs(nums[i+1]-nums[i])+Math.abs(nums[i]-nums[nums.length-1]));
        }
        int small_max=Integer.MIN_VALUE;
        int big_min=Integer.MAX_VALUE;
        for(int i=1;i<nums.length;i++){
            small_max=Math.max(small_max,Math.min(nums[i],nums[i-1]));
            big_min=Math.min(big_min,Math.max(nums[i],nums[i-1]));
        }
        return Math.max(count,chushi+2*(small_max-big_min));     
    }
}

总结

• 分析出几种情况，然后分别对各个情况实现