1330. 反转子数组以最大化数组价值

Hard

题目描述

给你一个整数数组 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^4
-10^5 <= nums[i] <= 10^5
答案保证能够用 32 位整数表示。

解题思路

这道题的关键在于理解反转子数组对数组价值的影响。

当我们反转子数组 [L, R] 时，数组价值的变化来自于边界处的差异：

原来的连接：a[L-1] 连接 a[L]，a[R] 连接 a[R+1]
反转后的连接：a[L-1] 连接 a[R]，a[L] 连接 a[R+1]

因此，价值的变化量为： |a[L-1] - a[R]| + |a[L] - a[R+1]| - |a[L-1] - a[L]| - |a[R] - a[R+1]|

由于绝对值函数的性质，我们需要考虑四种情况来最大化这个表达式：

(a[R] - a[L-1]) + (a[R+1] - a[L])
(a[R] - a[L-1]) + (a[L] - a[R+1])
(a[L-1] - a[R]) + (a[R+1] - a[L])
(a[L-1] - a[R]) + (a[L] - a[R+1])

为了高效计算，我们可以重写这些表达式：

Case 1: (a[R] + a[R+1]) - (a[L-1] + a[L])
Case 2: (a[R] - a[R+1]) - (a[L-1] - a[L])
Case 3: -(a[R] - a[R+1]) + (a[L-1] - a[L])
Case 4: -(a[R] + a[R+1]) + (a[L-1] + a[L])

对于每种情况，我们维护前缀最大值和最小值来高效计算所有可能的 L,R 组合。

算法步骤：

计算原数组的价值
对每个可能的右边界 R，使用前缀最值来计算四种情况的最大增益
返回原价值加上最大增益

代码实现

class Solution {
public:
    int maxValueAfterReverse(vector<int>& nums) {
        int n = nums.size();
        
        // 计算原始价值
        int originalValue = 0;
        for (int i = 0; i < n - 1; i++) {
            originalValue += abs(nums[i] - nums[i + 1]);
        }
        
        int maxGain = 0;
        
        // 处理边界情况：反转从开头开始或到结尾结束的子数组
        for (int i = 1; i < n; i++) {
            // 反转 [0, i]
            maxGain = max(maxGain, abs(nums[i] - nums[i - 1]) - abs(nums[0] - nums[1]));
        }
        for (int i = 0; i < n - 1; i++) {
            // 反转 [i, n-1]
            maxGain = max(maxGain, abs(nums[i] - nums[i + 1]) - abs(nums[n - 2] - nums[n - 1]));
        }
        
        // 处理一般情况：反转中间的子数组
        for (int case_type = 0; case_type < 4; case_type++) {
            int maxPrefix = INT_MIN;
            
            for (int r = 1; r < n - 1; r++) {
                int left_val, right_val;
                
                switch (case_type) {
                    case 0:
                        left_val = nums[r - 1] + nums[r];
                        right_val = nums[r] + nums[r + 1];
                        break;
                    case 1:
                        left_val = nums[r - 1] - nums[r];
                        right_val = nums[r] - nums[r + 1];
                        break;
                    case 2:
                        left_val = -nums[r - 1] + nums[r];
                        right_val = -nums[r] + nums[r + 1];
                        break;
                    case 3:
                        left_val = -nums[r - 1] - nums[r];
                        right_val = -nums[r] - nums[r + 1];
                        break;
                }
                
                maxPrefix = max(maxPrefix, left_val);
                int gain = maxPrefix + right_val - abs(nums[r - 1] - nums[r]) - abs(nums[r] - nums[r + 1]);
                maxGain = max(maxGain, gain);
            }
        }
        
        return originalValue + maxGain;
    }
};

class Solution:
    def maxValueAfterReverse(self, nums: List[int]) -> int:
        n = len(nums)
        
        # 计算原始价值
        original_value = sum(abs(nums[i] - nums[i + 1]) for i in range(n - 1))
        
        max_gain = 0
        
        # 处理边界情况：反转从开头开始或到结尾结束的子数组
        for i in range(1, n):
            # 反转 [0, i]
            max_gain = max(max_gain, abs(nums[i] - nums[i - 1]) - abs(nums[0] - nums[1]))
        
        for i in range(n - 1):
            # 反转 [i, n-1]
            max_gain = max(max_gain, abs(nums[i] - nums[i + 1]) - abs(nums[n - 2] - nums[n - 1]))
        
        # 处理一般情况：反转中间的子数组
        for case_type in range(4):
            max_prefix = float('-inf')
            
            for r in range(1, n - 1):
                if case_type == 0:
                    left_val = nums[r - 1] + nums[r]
                    right_val = nums[r] + nums[r + 1]
                elif case_type == 1:
                    left_val = nums[r - 1] - nums[r]
                    right_val = nums[r] - nums[r + 1]
                elif case_type == 2:
                    left_val = -nums[r - 1] + nums[r]
                    right_val = -nums[r] + nums[r + 1]
                else:
                    left_val = -nums[r - 1] - nums[r]
                    right_val = -nums[r] - nums[r + 1]
                
                max_prefix = max(max_prefix, left_val)
                gain = max_prefix + right_val - abs(nums[r - 1] - nums[r]) - abs(nums[r] - nums[r + 1])
                max_gain = max(max_gain, gain)
        
        return original_value + max_gain

public class Solution {
    public int MaxValueAfterReverse(int[] nums) {
        int n = nums.Length;
        
        // 计算原始价值
        int originalValue = 0;
        for (int i = 0; i < n - 1; i++) {
            originalValue += Math.Abs(nums[i] - nums[i + 1]);
        }
        
        int maxGain = 0;
        
        // 处理边界情况：反转从开头开始或到结尾结束的子数组
        for (int i = 1; i < n; i++) {
            // 反转 [0, i]
            maxGain = Math.Max(maxGain, Math.Abs(nums[i] - nums[i - 1]) - Math.Abs(nums[0] - nums[1]));
        }
        
        for (int i = 0; i < n - 1; i++) {
            // 反转 [i, n-1]
            maxGain = Math.Max(maxGain, Math.Abs(nums[i] - nums[i + 1]) - Math.Abs(nums[n - 2] - nums[n - 1]));
        }
        
        // 处理一般情况：反转中间的子数组
        for (int caseType = 0; caseType < 4; caseType++) {
            int maxPrefix = int.MinValue;
            
            for (int r = 1; r < n - 1; r++) {
                int leftVal, rightVal;
                
                switch (caseType) {
                    case 0:
                        leftVal = nums[r - 1] + nums[r];
                        rightVal = nums[r] + nums[r + 1];
                        break;
                    case 1:
                        leftVal = nums[r - 1] - nums[r];
                        rightVal = nums[r] - nums[r + 1];
                        break;
                    case 2:
                        leftVal = -nums[r - 1] + nums[r];
                        rightVal = -nums[r] + nums[r + 1];
                        break;
                    default:
                        leftVal = -nums[r - 1] - nums[r];
                        rightVal = -nums[r] - nums[r + 1];
                        break;
                }
                
                maxPrefix = Math.Max(maxPrefix, leftVal);
                int gain = maxPrefix + rightVal - Math.Abs(nums[r - 1] - nums[r]) - Math.Abs(nums[r] - nums[r + 1]);
                maxGain = Math.Max(maxGain, gain);
            }
        }
        
        return originalValue + maxGain;
    }
}

var maxValueAfterReverse = function(nums) {
    const n = nums.length;
    
    // 计算原始价值
    let originalValue = 0;
    for (let i = 0; i < n - 1; i++) {
        originalValue += Math.abs(nums[i] - nums[i + 1]);
    }
    
    let maxGain = 0;
    
    // 处理边界情况：反转从开头开始或到结尾结束的子数组
    for (let i = 1; i < n; i++) {
        // 反转 [0, i]
        maxGain = Math.max(maxGain, Math.abs(nums[i] - nums[i - 1]) - Math.abs(nums[0] - nums[1]));
    }
    
    for (let i = 0; i < n - 1; i++) {
        // 反转 [i, n-1]
        maxGain = Math.max(maxGain, Math.abs(nums[i] - nums[i + 1]) - Math.abs(nums[n - 2] - nums[n - 1]));
    }
    
    // 处理一般情况：反转中间的子数组
    for (let caseType = 0; caseType < 4; caseType++) {
        let maxPrefix = -Infinity;
        
        for (let r = 1; r < n - 1; r++) {
            let leftVal, rightVal;
            
            switch (caseType) {
                case 0:
                    leftVal = nums[r - 1] + nums[r];
                    rightVal = nums[r] + nums[r + 1];
                    break;
                case 1:
                    leftVal = nums[r - 1] - nums[r];
                    rightVal = nums[r] - nums[r + 1];
                    break;
                case 2:
                    leftVal = -nums[r - 1] + nums[r];
                    rightVal = -nums[r] + nums[r + 1];
                    break;
                case 3:
                    leftVal = -nums[r - 1] - nums[r];
                    rightVal = -nums[r] - nums[r + 1];
                    break;
            }
            
            maxPrefix = Math.max(maxPrefix, leftVal);
            const gain = maxPrefix + rightVal - Math.abs(nums[r - 1] - nums[r]) - Math.abs(nums[r] - nums[r + 1]);
            maxGain = Math.max(maxGain, gain);
        }
    }
    
    return originalValue + maxGain;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	值
时间复杂度	O(n)
空间复杂度	O(1)

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析