2023-05-12每日一题

一、题目编号

1330. 翻转子数组得到最大的数组值

二、题目链接

点击跳转到题目位置

三、题目描述

给你一个整数数组 nums 。「数组值」定义为所有满足 0 <= i < nums.length-1 的 |nums[i]-nums[i+1]| 的和。

你可以选择给定数组的任意子数组，并将该子数组翻转。但你只能执行这个操作 一次 。

请你找到可行的最大 数组值 。

四、解题代码

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

五、解题思路

(1) 首先先计算整体的（即）不变的值，为res1，即一次枚举，按照题目要求计算即可。

(2) 接着我们思考一个问题，加入我们将位置i 到 位置j 的数字颠倒，实际上中间的子数组的数组值并没有发生改变，实际上变化的只是边缘的值，因而我们可以思考交换的位置所影响的边缘位置的数组值。

(3) 首先思考左端(下边为0)到右边一个下标i的子数组进行翻转，意味着实际变化的值为abs(nums[0] - nums[i+1]) - abs(nums[i] - nums[i+1])，记录一个最大值为res1。

(4) 接着思考右端（下标为n-1）到左边一个下标为i的子数组进行翻转，意味着实际变化的值为nums[n - 1] - nums[i - 1]) - abs(nums[i] - nums[i - 1])，记录为最大值为res1，实际上就是更新res1。

(5) 最后思考的是 下标为i 的数 到下标为 j 数之间的子数组翻转。此时改变的值为abs(nums[j] - nums[i-1]) + abs(nums[j+1] - nums[i]) - abs(nums[i] - nums[i-1]) - abs(nums[j+1] - nums[j-1])。分别记录nums[i-1] = a，nums[i] = b, nums[j] = c， nums[j+1] = d。 根据a、b、c、d四个值的大小可以得到不同的可能性。最后得出结论当两个相邻数对，当一个数对的较大值小于另一个数对的较小值时，求差值的两倍。

(6) 最后得出最大值即可。