解题思路

我们需要在两个数组中各选出一个非空子数组（实际上是“子序列”——可以删掉若干元素但保持相对顺序），要求两者长度相同，使得

最大，其中 $x_i$ 是第一个数组子数组中的元素，$y_i$ 是第二个数组子数组中的对应元素。

题目内容

给你两个数组，请你返回这两个数组长度相同的非空子数组的最大绝对差和。数组的绝对差和是指两个长度相同的数组，对应位置的数值的差的绝对值，然后求和。例如：数组$1$为$[1\ 2]$，数组$2$为$[3\ 4]$，它们的绝对差和是$|1-3| + |2-4| = 2 + 2 = 4$。数组的非空子数组是通过删除数组中某些元素（可能不删除）后剩余节点组成的数组，且不能改变数组的相对顺序。比如：$[2\ 3\ 5]$是$[1\ 2\ 3\ 4\ 5]$的一个子数组，而数组$[1\ 5\ 3]$则不是，因为顺序与原数组不一致。

输入描述

第1行：$N，M，N$表示数组1的长度，$M$表示数组$2$的长度。N,M的范围是$[1,500]$

第2行：数组$1$中的存储的数，个数为$N$，数组中数值的范围是$[-1000,100]$

第3行：数组$2$中存储的数，个数为$M$，数组中数值的范围是$[-1000,100]$

输出描述

子数组的最大绝对差和

样例1

输入

3 3
1 3 5
2 4 6

输出

6

说明

子数组长度为1的子数组的差和如下：

第1个数组长度为1的子数组[1]，第2个数组长度为1的子数组[2]，绝对差和为$|1-2|=1$

第1个数组长度为1的子数组[1]，第2个数组长度为1的子数组[4]，绝对差和为$|1-4|=3$

第1个数组长度为1的子数组[1]，第2个数组长度为1的子数组[6]，绝对差和为$|1-6|=5$

第1个数组长度为1的子数组[3]，第2个数组长度为1的子数组[2]，绝对差和为$|3-2|=1$

第1个数组长度为1的子数组[3]，第2个数组长度为1的子数组[4]，绝对差和为$|3-4|=1$

第1个数组长度为1的子数组[3]，第2个数组长度为1的子数组[6]，绝对差和为$|3-6|=3$

第1个数组长度为1的子数组[5]，第2个数组长度为1的子数组[2]，绝对差和为$|5-2|=3$

第1个数组长度为1的子数组[5]，第2个数组长度为1的子数组[4]，绝对差和为$|5-4|=1$

第1个数组长度为1的子数组[5]，第2个数组长度为1的子数组[6]，绝对差和为$|5-6|=1$

子数组长度为2的子数组的差和如下：

第1个数组长度为2的子数组[1,3]，第2个数组长度为2的子数组[2,4]，绝对差和为$|1-2|+|3-4|=2$

第1个数组长度为2的子数组[1,3]，第2个数组长度为2的子数组[4,6]，绝对差和为$|1-4|+|3-6|=6$

第1个数组长度为2的子数组[1,5]，第2个数组长度为2的子数组[2,4]，绝对差和为$|1-2|+|5-4|=2$

第1个数组长度为2的子数组[1,5]，第2个数组长度为2的子数组[4,6]，绝对差和为$|1-4|+|5-6|=4$

第1个数组长度为2的子数组[3,5]，第2个数组长度为2的子数组[2,4]，绝对差和为$|3-2|+|5-4|=2$

第1个数组长度为2的子数组[3,5]，第2个数组长度为2的子数组[4,6]，绝对差和为$|3-4|+|5-6|=2$

子数组长度为3的子数组的差和如下：

第1个数组长度为3的子数组[1,3,5]，第2个数组长度为3的子数组[2,4,6]，绝对差和为$|1-2|+|3-4|+|5-6|=3$

从数组1中得到子数组[1,3,5]，从数组2中得到子数组[4,6]，得到他们的最大绝对差和为

$|1-4|+|3-6|=6$

样例2

输入

2 2
1 2
3 4

输出

4

说明

子数组长度为1的子数组的差和如下：

第1个数组长度为1的子数组[1]，第2个数组长度为1的子数组[3]，绝对差和为$|1-3|=2$

第1个数组长度为1的子数组[1]，第2个数组长度为1的子数组[4]，绝对差和为$|1-4|=3$

第1个数组长度为1的子数组[2]，第2个数组长度为1的子数组[3]，绝对差和为$|2-3|=1$

第1个数组长度为1的子数组[2]，第2个数组长度为1的子数组[4]，绝对差和为$|2-4|=2$

子数组长度为2的子数组的差和如下：

第1个数组长度为2的子数组[1,2]，第2个数组长度为2的子数组[3,4]，绝对差和为$|1-3|+|2-4|=4$

最终：

从数组1中得到子数组[1,2]，数组2中得到子数组[3,4]，得到它们的最大绝对差和为

$|1-3|+|2-4|=4$