题目内容

小红有两个长度均为 $n$ 数组 $a$ 和 $b$ 。

对于这两个数组，当这两个数组满足 $(\sum\limits_{i=2}^n |a_i-a_{i-1}|) + (\sum\limits_{i=2}^n |b_i-b_{i-1}|)$ 的和最大时，称这两个数组是一个好数组对。

思路：动态规划

状态定义：

考虑 $val[i][0]$ 表示只考虑前 $i$ 个数，第 $i$ 个数，$a_i$ 与 $b_i$ 不交换的情况下，可以获得的相邻数的差值绝对值之和的最大值。
考虑 $val[i][1]$ 表示只考虑前 $i$ 个数，第 $i$ 个数，$a_i$ 与 $b_i$ 交换的情况下，可以获得的相邻数的差值绝对值之和的最大值。

状态转移：

$val[i][0]=\max(val[i - 1][0] + abs(a[i] - a[i - 1]) + abs(b[i] - b[i - 1]), val[i - 1][1] + abs(a[i] - b[i - 1]) + abs(b[i] - a[i - 1]))$