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

Categories:

题目描述
思路分析
1. 解法一：枚举边界 + 内部最优（推荐）
相似题目

题目描述

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

思路分析

解法一：枚举边界 + 内部最优（推荐）

核心思路：

设原始数组值为 base = sum |a[i] - a[i-1]|。

反转子数组只影响边界两处，枚举与首尾相连的情况求最大增益。

内部反转的最优增益可化简为 2 * (maxMin - minMax)。

复杂度分析：

时间复杂度：O(n)，一次扫描。

空间复杂度：O(1)。

class Solution {
    public int maxValueAfterReverse(int[] nums) {
        int n = nums.length;
        int base = 0;
        for (int i = 1; i < n; i++) {
            base += Math.abs(nums[i] - nums[i - 1]);
        }

        int best = 0;
        for (int i = 1; i < n; i++) {
            int gain1 = Math.abs(nums[0] - nums[i]) - Math.abs(nums[i] - nums[i - 1]);
            int gain2 = Math.abs(nums[n - 1] - nums[i - 1]) - Math.abs(nums[i] - nums[i - 1]);
            best = Math.max(best, Math.max(gain1, gain2));
        }

        int maxMin = Integer.MIN_VALUE;
        int minMax = Integer.MAX_VALUE;
        for (int i = 1; i < n; i++) {
            int a = nums[i - 1];
            int b = nums[i];
            int mn = Math.min(a, b);
            int mx = Math.max(a, b);
            maxMin = Math.max(maxMin, mn);
            minMax = Math.min(minMax, mx);
        }
        best = Math.max(best, 2 * (maxMin - minMax));

        return base + best;
    }
}

func maxValueAfterReverse(nums []int) int {
    n := len(nums)
    base := 0
    for i := 1; i < n; i++ {
        base += abs(nums[i] - nums[i-1])
    }

    best := 0
    for i := 1; i < n; i++ {
        gain1 := abs(nums[0]-nums[i]) - abs(nums[i]-nums[i-1])
        gain2 := abs(nums[n-1]-nums[i-1]) - abs(nums[i]-nums[i-1])
        if gain1 > best {
            best = gain1
        }
        if gain2 > best {
            best = gain2
        }
    }

    maxMin := -1 << 60
    minMax := 1 << 60
    for i := 1; i < n; i++ {
        a := nums[i-1]
        b := nums[i]
        mn := a
        if b < mn {
            mn = b
        }
        mx := a
        if b > mx {
            mx = b
        }
        if mn > maxMin {
            maxMin = mn
        }
        if mx < minMax {
            minMax = mx
        }
    }

    cand := 2 * (maxMin - minMax)
    if cand > best {
        best = cand
    }

    return base + best
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

相似题目

题目	难度	考察点
42. 接雨水	困难	边界优化
121. 买卖股票的最佳时机	简单	一次扫描
122. 买卖股票的最佳时机 II	中等	贪心
152. 乘积最大子数组	中等	动态规划
238. 除自身以外数组的乘积	中等	前后缀

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/47747422