Leetcode 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

解题思路

我们可以假设子数组的区间在[i+1,j]，那么反转前后只有i+1和j位置的数组值会发生变化（取i+1的目的是便于处理）。反转前为|nums[i]-nums[i+1]|+|nums[j]-nums[j+1]|，反转后为|nums[i]-nums[j]|+|nums[i+1]-nums[j+1]|，那么我们的目的就是希望前后插值尽可能大。

有两个边界条件需要处理：1）恰好i+1位于数组nums的左边界。 2）恰好j位于数组nums的右边界。

class Solution:
    def maxValueAfterReverse(self, nums: List[int]) -> int:
        n, res, d = len(nums), 0, 0
        for i in range(n - 1):
            res += abs(nums[i] - nums[i + 1])

        for j in range(n - 1):
            for i in range(j):
                d = max(d, abs(nums[i] - nums[j]) + 
                        abs(nums[i + 1] - nums[j + 1]) - 
                        abs(nums[i] - nums[i + 1]) - 
                        abs(nums[j] - nums[j + 1]))
                
        for i in range(n - 1):
            d = max(d, abs(nums[i] - nums[-1]) - 
                        abs(nums[i] - nums[i + 1]))
        for j in range(n - 1):
            d = max(d, abs(nums[0] - nums[j + 1]) - 
                        abs(nums[j] - nums[j + 1]))
        return res + d

但是这么做会超时，所以我们需要优化。

设$a=nums[i],b=nums[i+1],c=nums[j],d=nums[j+1]$，此时交换$b$和$c$的位置，那么变化前后的差值就是

• $\delta =|a-c|+|b-d|-|a-b|-|c-d|$。

设$L[i]=min(a,b),H[i]=max(a,b),L[j]=min(c,d),H[j]=max(c,d)$，那么如果区间$[L[i],H[i]]$和区间$[L[j],H[j]]$相交。

L[i]---------------H[i]
         |          |
        L[j]----------------H[j]

那么此时交换$H[i]$和$L[j]$后

L[i]----H[i]
         |          |
                   L[j]-----H[j]

前后的变化$\delta =-区间的交集\ast 2$。同理，如果区间$[L[i],H[i]]$和区间$[L[j],H[j]]$不相交的话，$\delta =区间的交集\ast 2$，所以我们现在的目标就是让L[j]-H[i]最大。

最后，需要考虑i和j在边界的情况，在文章一开始的时候我们就提及过了。

class Solution:
    def maxValueAfterReverse(self, nums: List[int]) -> int:
        total, res, Hi, Lj = 0, 0, float('inf'), -float('inf')
        for a, b in zip(nums, nums[1:]):
            total += abs(a - b)
            Hi, Lj = min(Hi, max(a, b)), max(Lj, min(a, b))
            res = max(res, abs(nums[0] - b) - abs(a - b), 
                      abs(a - nums[-1]) - abs(a - b), 
                     (Lj - Hi) * 2)
        return total + res

reference:

https://leetcode.com/problems/reverse-subarray-to-maximize-array-value/discuss/489968/O(n)-Java-with-Mathematical-Proof

https://leetcode.com/problems/reverse-subarray-to-maximize-array-value/discuss/489743/JavaC%2B%2BPython-One-Pass-O(1)-Space

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题，希望大家指出！！！

最后

以上就是生动发卡为你收集整理的Leetcode 1330：翻转子数组得到最大的数组值（超详细的解法！！！）的全部内容，希望文章能够帮你解决Leetcode 1330：翻转子数组得到最大的数组值（超详细的解法！！！）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。