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

正文索引 [隐藏]

题目大意

给你一个数组 $A$, 你可以将它的一个子区间翻转(也可以不翻转),求最大的

\sum_i |A_i – A_{i + 1}|

分析

首先,题目有一些特殊情况:

  • 不反转
  • 翻转区间从原区间头开始
  • 翻转区间到原区间尾结束

不看上面的三种特殊情况,普通情况可以被描述成这样(虚线是包裹住的是要翻转的区间):
普通翻转情况

很容易知道一点:翻转区间操作仅与边界处的四个数字有关系。因为目标式是相邻两个元素差值之和,翻转操作仅改变边界四个数字的相邻关系,其他都不改变。

假设不翻转时目标式的值为 $sum$,我们其实是要求一个 $sum + \max{delta}$,其中 $delta$ 时翻转操作对于答案的改变。

假设,不翻转时目标式的值为 $sum$,我们其实是要求一个 $sum + \max{delta}$,其中 $delta$ 时翻转操作对于答案的改变。

看一下 $delta$ 等于什么:

delta = -|A_a – A_b| – |A_c – A_d| + |A_a – A_c| + |A_b – A_d|

乍一看好像没啥,但其实 $A_a, A_b$ 与$A_c,A_d$ 在原数组中分别相邻,图中的虚线分别可以确定它们。那么 $-|A_a – A_b|$ 与 $-|A_c – A_d|$ 其实是一个虚线独立项,$|A_a – A_c| + |A_b – A_d|$ 是一个有交叉信息项。

说白一点,翻转区间的左端点与右端点知其一就可以知道对应的虚线独立项的值,左右端点必须同时知道才可以知道交叉信息项的值。独立项简单,交叉项难搞需要 $O(n^2)$ 枚举才行。

交叉项的形式其实是一个曼哈顿距离的形式,我们令:

\begin{cases}
A_a = x_0,\\
A_b = y_0,\\
A_c = x_1,\\
A_d = y_1.
\end{cases}

那么,原来的 $delta$ 表示为:

\begin{aligned}
delta = -|x_0 – y_0| – |x_1 – y_1| + |x_0 – x_1| + |y_0 – y_1|\\
= -|x_0 – y_0| – |x_1 – y_1| + (|x_0 – x_1| + |y_0 – y_1|)
\end{aligned}

后面就是一个曼哈顿距离,前面是点独立的信息,我们要求 $delta$ 的最大值。

这样这道题目就解出来了,我们可以套用求曼哈顿距离最大的是方法求这题的答案。

曼哈顿距离有一个转化形式:

\begin{aligned}
|x_0 – x_1| + |y_0 – y_1| = \max\{&(x_0+y_0) – (x_1+y_1),\\
&(x_0-y_0) – (x_1-y_1),\\
&(-x_0+y_0) – (-x_1+y_1),\\
&(-x_0-y_0) – (-x_1-y_1)
\}
\end{aligned}

所以求一堆点之间的最大曼哈顿距离,只需要将点按四种情况($+x+y$,$-x+y$,$+x-y$,$-x-y$)分别计算值,然后求得每种情况下的最大差取 Max 即可。

针对这道题目,每个点还有自己独立的信息,也是很容易加入的,并使用一样的处理方法,就可以求得 $delta$ 的最大值:

\begin{aligned}
-|x_0 – y_0| – |x_1 – y_1| + (|x_0 – x_1| + |y_0 – y_1|) = \max\{&(x_0+y_0-|x_0 – y_0|) – (x_1+y_1+ |x_1 – y_1|),\\
&(x_0-y_0-|x_0 – y_0|) – (x_1-y_1+ |x_1 – y_1|),\\
&(-x_0+y_0-|x_0 – y_0|) – (-x_1+y_1+ |x_1 – y_1|),\\
&(-x_0-y_0-|x_0 – y_0|) – (-x_1-y_1+ |x_1 – y_1|)
\}
\end{aligned}

剩余就是几种特殊情况了,都是 $O(n)$ 级别的,直接暴力比一比就行了。

代码