LeetCode 1330. 翻转子数组得到最大的数组值
目录
题目描述
题意分析
数组的「数组值」定义为所有相邻元素差的绝对值之和，也就是
sum |nums[i] - nums[i-1]|。你必须恰好执行一次子数组翻转（子数组长度可以为 1，此时相当于什么都没做），问翻转后数组值最大能是多少。返回的是这个最大值本身，不是翻转的位置。「恰好一次且允许长度为 1」这句话的实际含义是：不翻转永远是一个合法候选，所以答案一定不小于原数组值，增益部分取不到正数时就取 0。
约束里
nums.length最大3 * 10^4，而子数组的选法有 $O(n^2)$ 种，说明枚举左右端点这条路一定会超时，必须找到能把两个端点解耦的结构。元素范围-10^5 <= nums[i] <= 10^5允许负数，所以不能想当然地把绝对值直接拆成减法。真正的题眼藏在「翻转」这个操作本身：把
[l, r]这段倒过来，段内部所有相邻对只是被整体反序，每一对的两个元素还是同一对，绝对值不变；段外的相邻对更是完全没被碰到。会变的只有两处接缝——(l-1, l)变成(l-1, r)，(r, r+1)变成(l, r+1)。整道题就是围绕这两处接缝做文章。边界：
n == 1时一个相邻对都没有，数组值恒为 0，任何翻转都改变不了；n == 2时翻转只是交换两个元素，绝对差不变，答案还是原值。这两种情况必须让代码自然给出 0 和原值，而不是被中间推导出来的公式污染。
解法：枚举边界 + 内部最优
核心思路
从暴力开始：枚举左右端点
l <= r，每次按上面的接缝分析用 $O(1)$ 算出增益，总共 $O(n^2)$。n = 3 * 10^4时是 $9 \times 10^8$ 次运算，超时。瓶颈在于l和r被绑在一起枚举，而增益公式里它们其实只通过「各自那一侧的接缝」发生联系。把增益写清楚。记
a = nums[l-1]、b = nums[l]、c = nums[r]、d = nums[r+1]，则翻转[l, r]的增益是delta = |a-c| + |b-d| - |a-b| - |c-d|。按接缝是否存在分成三类，正好对应代码里的三段。第一类，
l == 0：左接缝不存在，只剩右接缝，delta = |nums[0] - nums[r+1]| - |nums[r] - nums[r+1]|。第二类，r == n-1：右接缝不存在，delta = |nums[l-1] - nums[n-1]| - |nums[l-1] - nums[l]|。这两类各只依赖一个下标，扫一遍就能取到最大值。第三类是内部翻转，两个接缝都在。这里需要一个关键的观察：把
(a, b)看成数轴上的闭区间I1 = [min(a,b), max(a,b)]，把(c, d)看成I2 = [min(c,d), max(c,d)]，则|a-b|与|c-d|分别是两个区间的长度。当两个区间相交时，无论怎么配对，|a-c| + |b-d|都不会超过|a-b| + |c-d|，增益非正；只有当两个区间完全分离时才有正增益，且此时delta = 2 * (较高区间的最小值 - 较低区间的最大值)。这个式子的威力在于它把两个端点彻底解耦了：要让
2 * (min(I2) - max(I1))最大，只需要在所有相邻对里分别取「区间下端的最大值」和「区间上端的最小值」，两者可以来自任意两个不同的相邻对。于是内部翻转的最优增益就是2 * (maxMin - minMax)，其中maxMin = max over i of min(nums[i-1], nums[i])，minMax = min over i of max(nums[i-1], nums[i])。顺带一提，如果这两个极值恰好来自同一个相邻对，那么
maxMin <= minMax，算出来的候选值非正，会被「不翻转」的 0 兜底掉，不会产生非法答案，因此不需要额外判断两个极值是否同源。最终答案 =
base + max(0, 三类候选的最大值)，其中base是原数组值。整个过程三次线性扫描，$O(n)$ 时间、$O(1)$ 空间。
解题步骤
- 先算
base：一次遍历累加|nums[i] - nums[i-1]|。这是不翻转时的答案，后面所有工作都只是在它上面加一个非负增益。best初始化为 0：因为翻转长度为 1 的子数组等价于不动，0 永远是一个合法增益。初始化成负无穷会让没有正增益的输入返回一个比base小的错误值。- 扫前缀候选：对每个
i（1 <= i <= n-1）计算|nums[0] - nums[i]| - |nums[i] - nums[i-1]|，对应翻转[0, i-1]后新接缝落在(nums[0], nums[i])。注意新接缝的左端是nums[0]而不是nums[i-1]——翻转后原来的首元素被推到了i-1的位置。- 扫后缀候选：对每个
i计算|nums[n-1] - nums[i-1]| - |nums[i] - nums[i-1]|，对应翻转[i, n-1]后新接缝落在(nums[i-1], nums[n-1])。- 扫内部候选：同一趟遍历里维护
maxMin与minMax，结束后用2 * (maxMin - minMax)更新best。乘 2 不能漏——增益里左右两处接缝各贡献了一份。- 特判
n < 2直接返回 0：此时一个相邻对都没有，maxMin与minMax还停留在哨兵初值上，2 * (maxMin - minMax)会在 int 下溢出成一个正数并污染答案。- 返回
base + best。以
nums = [2, 3, 1, 5, 4]走一遍。第一步，
base = |3-2| + |1-3| + |5-1| + |4-5| = 1 + 2 + 4 + 1 = 8。第二步，前缀与后缀候选逐个
i算：i = 1得|2-3| - |3-2| = 0与|4-2| - |3-2| = 1；i = 2得|2-1| - |1-3| = -1与|4-3| - |1-3| = -1；i = 3得|2-5| - |5-1| = -1与|4-1| - |5-1| = -1；i = 4得|2-4| - |4-5| = 1与|4-5| - |4-5| = 0。这一轮best = 1。第三步，四个相邻对分别是
(2,3)、(3,1)、(1,5)、(5,4)，它们的min依次是 2、1、1、4，max依次是 3、3、5、5。于是maxMin = 4（来自(5,4)），minMax = 3（来自(2,3)或(3,1)），内部候选= 2 * (4 - 3) = 2 > 1，best更新为 2。返回
8 + 2 = 10。验证一下：maxMin来自下标 3、4 那一对，minMax来自下标 0、1 那一对，对应翻转[1, 3]，数组变成[2, 5, 1, 3, 4]，数组值= 3 + 4 + 2 + 1 = 10，与公式完全吻合。再看边界
nums = [5]：特判直接返回 0。若去掉这个特判，maxMin仍是Integer.MIN_VALUE、minMax仍是Integer.MAX_VALUE，maxMin - minMax在 int 下溢出成 1，best变成 2，函数会返回 2 这个凭空冒出来的值。
代码实现
class Solution {
public int maxValueAfterReverse(int[] nums) {
int n = nums.length;
// 没有相邻对时数组值恒为 0，同时避免下面的哨兵初值参与减法溢出。
if (n < 2) {
return 0;
}
int base = 0;
for (int i = 1; i < n; i++) {
base += Math.abs(nums[i] - nums[i - 1]);
}
// 翻转长度为 1 的子数组等价于不动，所以增益至少是 0。
int best = 0;
for (int i = 1; i < n; i++) {
// 翻转前缀 [0, i-1] 后，新接缝是 (nums[0], nums[i])。
int gain1 = Math.abs(nums[0] - nums[i]) - Math.abs(nums[i] - nums[i - 1]);
// 翻转后缀 [i, n-1] 后，新接缝是 (nums[i-1], nums[n-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)
// 没有相邻对时数组值恒为 0，直接返回。
if n < 2 {
return 0
}
base := 0
for i := 1; i < n; i++ {
base += abs(nums[i] - nums[i-1])
}
// 翻转长度为 1 的子数组等价于不动，所以增益至少是 0。
best := 0
for i := 1; i < n; i++ {
// 翻转前缀 [0, i-1] 后，新接缝是 (nums[0], nums[i])。
gain1 := abs(nums[0]-nums[i]) - abs(nums[i]-nums[i-1])
// 翻转后缀 [i, n-1] 后，新接缝是 (nums[i-1], nums[n-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
}
复杂度分析
- 时间复杂度：$O(n)$。三趟独立的线性扫描分别求
base、前后缀候选、内部候选，每趟循环体都是常数次绝对值与比较运算，没有任何嵌套枚举。- 空间复杂度：$O(1)$。只用了
base、best、maxMin、minMax这几个标量，没有开任何与n同阶的辅助数组——这正是把两个端点解耦之后才拿得到的收益。
关键点总结
- 局部操作只影响接缝：翻转、旋转、交换这类操作往往只改变常数处相邻关系，先把「变化量」写成一个只含少数几个元素的表达式，是把 $O(n^2)$ 压到 $O(n)$ 的通用第一步。
- 把绝对值翻译成区间：
|x - y|是数轴上一段区间的长度，两个相邻对的增益能否为正取决于两段区间是否分离。这个几何视角比硬拆max(x-y, y-x)更容易在白板上讲清楚。- 解耦即可分别取极值：一旦目标函数化成
f(左侧对) + g(右侧对)的形式，就可以对两项各自独立取最优，不必担心它们来自哪两个位置；同源时结果非正会被 0 兜底，这一步的自洽性要主动说出来。- 「至少不翻转」提供了天然下界：
best从 0 起步既是题意要求，也是保护所有推导式在退化输入上不越界的安全网。- 哨兵初值必须配特判：用
Integer.MIN_VALUE/Integer.MAX_VALUE做极值初值时，一旦循环一次都没跑，两者相减就会溢出。写完极值扫描立刻回头检查「循环体可能零次执行吗」。- 面试视角：这题的分数几乎全在推导上。正确的答题节奏是先说清「翻转只动两处接缝」，写出通用
delta公式，再分三类讨论，最后才落到十几行代码；直接背出2 * (maxMin - minMax)而讲不出区间分离的理由，会被追问到失分。
易错点总结
best初值写成Integer.MIN_VALUE：nums = [1, 2]时所有候选增益都不为正，best停在某个负数上，返回值比原数组值 1 还小。正确做法是从 0 起步。- 不特判
n < 2：nums = [5]时两个极值哨兵未被任何相邻对更新，2 * (Integer.MIN_VALUE - Integer.MAX_VALUE)在 int 下溢出成 2，函数返回 2 而不是 0。- 内部增益忘记乘 2：
nums = [2, 3, 1, 5, 4]的内部候选会算成 1，输不过前缀候选，最终返回 9 而不是 10。系数 2 来自左右两处接缝各贡献一份间隙。- 前缀候选下标写成
|nums[0] - nums[i-1]|：这相当于认为翻转[0, i-1]之后接缝右侧还是nums[i-1]，但它已经被换到了段首。nums = [2, 3, 1, 5, 4]在i = 4上会算出|2-5| - |4-5| = 2这个并不存在的增益。- 后缀候选误用
nums[i]当接缝左端：翻转[i, n-1]之后段左边的元素仍是nums[i-1]，写成nums[i]会把接缝算到段内部去，得到的增益与实际翻转结果对不上。- 只考虑内部翻转，漏掉前后缀两类：
nums = [1, 3, 2]这种最优解是翻转前缀或后缀的输入会返回偏小的值，因为内部翻转要求两侧接缝都存在，端点处根本不适用。- 把「区间分离」的判断写进循环里逐对配对：即先枚举两个相邻对再判断是否分离，这会退回 $O(n^2)$，
n = 3 * 10^4时超时。解耦之后压根不需要配对。- 误以为翻转会改变段内部的数组值：段内相邻对只是整体反序，
|x - y|与|y - x|相同，所以内部贡献一分不变。如果按「翻转后重算整段」来实现，不仅慢，还容易把接缝重复计一次。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 53. 最大子数组和 | 中等 | 同样是一次扫描维护候选最优，但状态是「前缀和的历史最小值」，不涉及绝对值拆解 |
| 152. 乘积最大子数组 | 中等 | 同样靠同时维护两个极值来覆盖符号翻转，本题维护的是 maxMin 与 minMax
|
| 918. 环形子数组的最大和 | 中等 | 把「跨越首尾」的情形改写成「总和减去最小子数组」，与本题按接缝分类讨论同源 |
| 1685. 有序数组中差绝对值之和 | 中等 | 也要消掉绝对值，但手法是排序后按大小关系拆成两段前缀和，而非区间分离 |
| 1191. K 次串联后最大子数组之和 | 中等 | 同样需要枚举「是否跨接缝」并把重复段折叠成常数个情形 |
| 862. 和至少为 K 的最短子数组 | 困难 | 同为把 $O(n^2)$ 的端点枚举降到线性，但工具是前缀和加单调队列 |
| 560. 和为 K 的子数组 | 中等 | 端点解耦的另一种形态：固定右端后用哈希表一次性查完所有合法左端 |