原文链接: https://leetcode-cn.com/problems/reverse-subarray-to-maximize-array-value

英文原文

You are given an integer array nums. The value of this array is defined as the sum of |nums[i] - nums[i + 1]| for all 0 <= i < nums.length - 1.

You are allowed to select any subarray of the given array and reverse it. You can perform this operation only once.

Find maximum possible value of the final array.

 

Example 1:

Input: nums = [2,3,1,5,4]
Output: 10
Explanation: By reversing the subarray [3,1,5] the array becomes [2,5,1,3,4] whose value is 10.

Example 2:

Input: nums = [2,4,9,24,2,1,10]
Output: 68

 

Constraints:

• 1 <= nums.length <= 3 * 104
• -105 <= nums[i] <= 105

中文题目

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

通过代码

高赞题解

解题思路

思路参考：@wnjxyk

拿到题目先做一些处理，发现一个简单的性质:

我们假设反转[l,r]:
原数组 … a[l - 1] ,a[l] , … , a[r] , a[r + 1] …
反转后 … a[l - 1] , a[r] , … , a[l] , a[r + 1]…
通过计算发现发生改变的数值仅仅是两个端点

$减少的值 = abs(a[l] - a[l - 1]) + abs(a[r] - a[r + 1]);$
$增加的值 = abs(a[l - 1] - a[r]) + abs(a[l] - a[r + 1]);$
$变化的值 = abs(a[l - 1] - a[r]) + abs(a[l] - a[r + 1]) - (abs(a[l] - a[l - 1]) + abs(a[r] - a[r + 1]));$

说来惭愧比赛的时候我也就处理到这里了。
现在有一个很明显的$O(n^2)$的做法:暴力枚举区间
但看见数据范围的时候心里就一凉，$3 * 10^4$,O($n ^ 2$)是绝对过不去的。

其实我们可以深度挖掘一下这个式子，减少得值已经是单点的值了，不用管他。
我们再观察一下增加的值,这不就是曼哈顿距离嘛。。。

曼哈顿距离有一个暴力开绝对值的方法就是枚举四种情况，然后取max就可以了
$增加的值 = abs(a[l - 1] - a[r]) + abs(a[l] - a[r + 1])$ =
$max{$
$a[l - 1] + a[l] - (a[r] + a[r+1]) ,$
$a[l - 1] - a[l] - (a[r] - a[r + 1]),$
$-a[l - 1] + a[l] - (-a[r] + a[r + 1]),$
$-a[l - 1] - a[l] - (-a[r] - a[r + 1])$
$}$
最后把变化的值计算出来
$变化的值 =$
$max{$
$a[l - 1] + a[l] - abs(a[l] - a[l - 1]) - (a[r] + a[r + 1] + abs(a[r] - a[r + 1])),$
$a[l - 1] - a[l] - abs(a[l] - a[l - 1]) - (a[r] - a[r + 1] + abs(a[r] - a[r + 1])),$
$-a[l - 1] + a[l] - abs(a[l] - a[l - 1]) - (-a[r] + a[r + 1] + abs(a[r] - a[r + 1])),$
$-a[l - 1] - a[l] - abs(a[l] - a[l - 1]) - (-a[r] - a[r + 1] + abs(a[r] - a[r + 1]))$
$}$
这样我们就得到了由单点决定的变化的值

算法

(贪心) O(n)

我们先把不用反转区间的值算出来,记为res，

然后分情况讨论计算出减号左边的数减号右边的数，

分别求最大值和最小值，用最大值 - 最小值就是最大变化数

最后最大变化数 + res相加就是本题的答案

ps:可以通过单独处理边界来减少写代码的难度

代码

class Solution {
public:
    int get_max(vector<int> &v)
    {
        int res = INT_MIN;
        for(auto x : v)
            res = max(res,x);
        
        return res;
    }
    int get_min(vector<int> &v)
    {
        int res = INT_MAX;
        for(auto x : v)
            res = min(res,x);
        
        return res;
    }
    int maxValueAfterReverse(vector<int>& nums) {
        int res = 0;
        int n = nums.size();
        
        for(int i=0;i<n-1;i++)
            res += abs(nums[i] - nums[i + 1]);
        
        int maxv = 0;

        for(int i=0;i<n;i++)
        {
            if(i != n - 1)
                maxv = max(maxv,abs(nums[0] - nums[i + 1]) - 
                                abs(nums[i] - nums[i + 1])); // 左端点为0右端点为i
            if(i != 0)
                maxv = max(maxv,abs(nums[n - 1] - nums[i - 1]) -
                                abs(nums[i] - nums[i - 1])); // 右端点为n-1,左端点为i
        }

        int mx[4] = {1,1,-1,-1};
        int my[4] = {1,-1,1,-1};
        
        for(int i=0;i<4;i++) // 枚举四种情况
        {
            vector<int> v1,v2;
            for(int j=0;j<n-1;j++)
            {
                int a = mx[i] * nums[j];
                int b = my[i] * nums[j + 1];
                int cur = abs(nums[j] - nums[j + 1]);
                v1.push_back(a + b - cur);
                v2.push_back(a + b + cur);
            }
            int a = get_max(v1);
            int b = get_min(v2);
            maxv = max(maxv,a - b);
        }

        return res + maxv;
    }
};

统计信息

通过次数	提交次数	AC比率
1218	3187	38.2%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言