LeetCode 1330. 翻转子数组得到最大的数组值
题目描述
题意分析
数组值是所有相邻元素绝对差的总和，要求翻转一个连续子数组后使它最大。翻转长度为 1 的区间不会改变数组，因此最优答案至少等于原数组值。
解法：枚举边界 + 内部最优
核心思路
[!blue]
翻转区间内部的相邻元素只交换方向，绝对差仍相同。真正改变的只有区间与外部连接的边，因此先求原数组值
base，再寻找最大的增益best，不需要实际翻转或重新求和。先处理只有一条外部边的情况。对相邻位置
i - 1、i，翻转前缀[0, i - 1]会把这条边替换为nums[0]与nums[i]的连接；翻转后缀[i, n - 1]则替换为nums[i - 1]与nums[n - 1]的连接。新边的绝对差减去旧边的绝对差，就是代码中的gain1、gain2，枚举所有i即可覆盖全部前后缀。
对不触及首尾的区间 [l, r]，令四个边界值为 $a=nums[l-1]$、$b=nums[l]$、$c=nums[r]$、$d=nums[r+1]$。旧边是 $(a,b)$、$(c,d)$，翻转后变成 $(a,c)$、$(b,d)$，增益为 $a-c + b-d - a-b - c-d $。 把旧边看成数轴上的两个区间，并将四个端点排序为 $x_1\le x_2\le x_3\le x_4$。任意配对的距离和都不超过两大端点之和减去两小端点之和。若两区间相交，旧边长度和已是这个上限 $(x_4-x_1)+(x_3-x_2)$，重新配对无法得到更大的和。若两区间分离，旧边长度和为 $(x_2-x_1)+(x_4-x_3)$，新边都跨过中间空隙，长度和变成 $(x_3-x_1)+(x_4-x_2)$，增益恰好是两倍空隙 $2(x_3-x_2)$。
因此只需在所有相邻对中，维护最大下端点
maxMin = max(min(a, b))和最小上端点minMax = min(max(a, b))，最大正空隙就是maxMin - minMax。差为正时，提供这两个端点的旧边在数轴上分离，不可能共用数组位置；按它们在数组中的先后顺序翻转中间部分，就能实现该增益。差不为正时没有内部正增益，用初始为 0 的best排除它即可。
解题步骤
- 原值累加全部相邻绝对差。
- 扫描前缀、后缀翻转的单接缝增益。
- 扫描相邻对极值得到内部候选。
- 把最大非负增益加回原值。
代码实现
class Solution {
public int maxValueAfterReverse(int[] nums) {
int n = nums.length;
if (n < 2) {
return 0;
}
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)
if n < 2 {
return 0
}
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 := nums[0]
minMax := nums[1]
if maxMin > minMax {
maxMin, minMax = minMax, maxMin
}
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
}
复杂度分析
- 时间复杂度：$O(n)$，三次独立线性扫描。
- 空间复杂度：$O(1)$，不实际修改数组。
关键点总结
[!green]
- 前后缀只有一处接缝，不能套内部两接缝公式。
- 单元素没有相邻对，直接返回零。
- 翻转整个数组也没有增益；初始
best = 0已覆盖所有不改善答案的选择。- 题面保证答案在 32 位整数范围内，原值又不超过答案，现有整数类型足够。
易错点总结
[!yellow]
- 只重算翻转区间内部、却漏算两处外部接缝，会遗漏实际变化的贡献。
- 内部候选漏乘二，会少算另一处接缝的收益。
- 只枚举内部翻转，会漏掉首尾边界的最优结果。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 396. 旋转函数 | 中等 | 同样通过推导操作前后的增量避免完整模拟，本题反转后内部相邻绝对差不变，只改变区间边界贡献。 |