[LeetCode] 1330. Reverse Subarray To Maximize Array Value #1330

grandyang · 2019-05-30T16:34:46Z

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 * 10^4
-10^5 <= nums[i] <= 10^5

这道题定义了一种数组值的计算方法，将每个数字和其右边一个数字的差的绝对值算出来，并加起来。现在说允许翻转任意一个子数组一次，让求出最大的数组值。就拿题目中的例子1来分析，如不翻转子数组的话，数组值的计算应为 1+2+4+1=8，若将子数组 [3,1,5] 翻转，得到新数组为 [2,5,1,3,4]，则数组值的计算为 3+4+2+1=10，这个是最大的，翻转其他任何子数组都无法超过这个值。题意搞懂了，下面就要来分析了，翻转子数组会对数组值造成什么影响，影响的是要翻转的边缘上的数字，我们让 a=2, b=3, c=5, d=4，那么原本是a和b，c和d之间相减，翻转之后就变成了a和c，b和d之间相减了，它们之间一定要存在某些关系，才能使得翻转后的数组值变大，对于下面这种情况，可以发现 max(a, b) < min(c, d)，这样交换之后的数组值是增加的：

2 | 3 1 5 | 4
a   b   c   d

对于如下这种情况，可以发现 max(a, b) = min(c, d)，这样交换之后的数组值是保持不变的：

2 | 3 1 5 | 3
a   b   c   d

对于如下这种情况，可以发现 max(a, b) > min(c, d)，这样交换之后的数组值是减少的：

4 | 3 1 5 | 3
a   b   c   d

综上所述，需要找到第一种情况，即 max(a, b) < min(c, d)。为了使其增幅最大，需要使得 max(a, b) 尽可能小，使得 min(c, d) 尽可能大，这样才能使得数组的增幅最大。于是只要遍历所有相邻的两个数字，分别计算出 minMax 和 maxMin 即可，而数组值的增幅其实就是 (maxMin - minMax)*2。

这里还需要考虑两种特殊情况，即翻转的子数组是从 nums[0] 其实的，或者是到 nums[n-1] 结束的，这样a活着d就不存在了。这两种 corner case 可以单独计算一下即可，参见代码如下：

class Solution {
public:
    int maxValueAfterReverse(vector<int>& nums) {
        int total = 0, res = 0, minMax = INT_MAX, maxMin = INT_MIN, n = nums.size();
        for (int i = 0; i < n - 1; ++i) {
            int diff = abs(nums[i] - nums[i + 1]);
            total += diff;
            res = max(res, abs(nums[0] - nums[i + 1]) - diff);
            res = max(res, abs(nums[n - 1] - nums[i]) - diff);
            minMax = min(minMax, max(nums[i], nums[i + 1]));
            maxMin = max(maxMin, min(nums[i], nums[i + 1]));
        }
        return total + max(res, (maxMin - minMax) * 2);
    }
};

Github 同步地址:

#1330

参考资料：

https://leetcode.com/problems/reverse-subarray-to-maximize-array-value/

https://leetcode.com/problems/reverse-subarray-to-maximize-array-value/solutions/489882/o-n-solution-with-explanation/

https://leetcode.com/problems/reverse-subarray-to-maximize-array-value/solutions/489743/java-c-python-one-pass-o-1-space/

LeetCode All in One 题目讲解汇总(持续更新中...)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

喜欢请点赞，疼爱请打赏❤️~.~