解题思路

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

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

把问题看成一个二维网格：

• 行是数组 A 的下标，列是数组 B 的下标。
• 如果我们选择把 A[i] 和 B[j] 配对，就相当于在网格中从 (i-1, j-1) 走到 (i, j)，并获得收益 $|A[i]-B[j]|$。
• 也可以选择跳过 A[i]（从 (i-1, j) 来）或跳过 B[j]（从 (i, j-1) 来），收益不变。

这就是一个典型的动态规划问题，形式与 LCS（最长公共子序列）类似，只是“匹配”两元素时得到的是权值 $|A[i]-B[j]|$。

设 dp[i][j] 表示使用 A 的前 i 个元素、B 的前 j 个元素能得到的最大绝对差和，则有转移：

• 跳过 A[i]：dp[i-1][j]
• 跳过 B[j]：dp[i][j-1]
• 同时取 A[i] 与 B[j] 作为一对：dp[i-1][j-1] + abs(A[i] - B[j])

取三者最大即可：

dp[i][j] = max(dp[i-1][j],dp[i][j-1], dp[i-1][j-1] + |A[i]-B[j]|)

边界：dp[0][*] = dp[*][0] = 0（选空子数组的得分为 0）。因为任意一对元素的绝对值差都 ≥ 0，所以最终 dp[N][M] 一定对应某个非空子数组（即使允许空子数组也不会更优），直接输出即可。

复杂度分析

• 时间复杂度：状态有 N * M 个，每个状态 O(1) 转移，故时间复杂度为 O(N * M)，在 N,M ≤ 500 时完全可行。
• 空间复杂度：使用二维数组存 dp，空间复杂度为 O(N * M)，约 25 万个整数，内存足够。若需要也可优化为两行滚动数组，但本题不必。

代码实现

Python

import sys

# 功能函数：计算两个数组子数组的最大绝对差和
def max_abs_diff_sum(a, b):
    n = len(a)
    m = len(b)
    # dp[i][j] 表示使用 a 前 i 个、b 前 j 个的最大绝对差和
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        ai = a[i - 1]
        for j in range(1, m + 1):
            # 三种转移：跳过 a[i]、跳过 b[j]、匹配 a[i] 和 b[j]
            dp[i][j] = max(
                dp[i - 1][j],                    # 跳过 a[i]
                dp[i][j - 1],                    # 跳过 b[j]
                dp[i - 1][j - 1] + abs(ai - b[j - 1])  # 匹配一对
            )
    return dp[n][m]


def main():
    data = list(map(int, sys.stdin.read().strip().split()))
    if not data:
        return
    # 读取 N, M
    N = data[0]
    M = data[1]
    # 读取两个数组
    a = data[2:2 + N]
    b = data[2 + N:2 + N + M]

    ans = max_abs_diff_sum(a, b)
    print(ans)


if __name__ == "__main__":
    main()

Java

import java.util.*;

// ACM 风格主类名必须为 Main
public class Main {

    // 功能函数：计算两个数组子数组的最大绝对差和
    public static int maxAbsDiffSum(int[] a, int[] b) {
        int n = a.length;
        int m = b.length;
        // dp[i][j] 表示使用 a 前 i 个、b 前 j 个的最大绝对差和
        int[][] dp = new int[n + 1][m + 1];

        for (int i = 1; i <= n; i++) {
            int ai = a[i - 1];
            for (int j = 1; j <= m; j++) {
                // 跳过 a[i]
                int skipA = dp[i - 1][j];
                // 跳过 b[j]
                int skipB = dp[i][j - 1];
                // 匹配 a[i] 和 b[j]
                int match = dp[i - 1][j - 1] + Math.abs(ai - b[j - 1]);
                // 三者取最大
                dp[i][j] = Math.max(Math.max(skipA, skipB), match);
            }
        }

        return dp[n][m];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 读取 N, M
        if (!sc.hasNextInt()) {
            return;
        }
        int N = sc.nextInt();
        int M = sc.nextInt();

        int[] a = new int[N];
        int[] b = new int[M];

        // 读取数组 1
        for (int i = 0; i < N; i++) {
            a[i] = sc.nextInt();
        }
        // 读取数组 2
        for (int i = 0; i < M; i++) {
            b[i] = sc.nextInt();
        }

        int ans = maxAbsDiffSum(a, b);
        System.out.println(ans);

        sc.close();
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

// 功能函数：计算两个数组子数组的最大绝对差和
int maxAbsDiffSum(const vector<int> &a, const vector<int> &b) {
    int n = (int)a.size();
    int m = (int)b.size();
    // dp[i][j] 表示使用 a 前 i 个、b 前 j 个的最大绝对差和
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

    for (int i = 1; i <= n; ++i) {
        int ai = a[i - 1];
        for (int j = 1; j <= m; ++j) {
            // 跳过 a[i]
            int skipA = dp[i - 1][j];
            // 跳过 b[j]
            int skipB = dp[i][j - 1];
            // 匹配 a[i] 和 b[j]
            int match = dp[i - 1][j - 1] + abs(ai - b[j - 1]);
            // 三者取最大
            dp[i][j] = max(max(skipA, skipB), match);
        }
    }
    return dp[n][m];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    if (!(cin >> N >> M)) {
        return 0;
    }

    vector<int> a(N), b(M);
    // 读取数组 1
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
    }
    // 读取数组 2
    for (int i = 0; i < M; ++i) {
        cin >> b[i];
    }

    int ans = maxAbsDiffSum(a, b);
    cout << ans << "\n";

    return 0;
}

题目内容

给你两个数组，请你返回这两个数组长度相同的非空子数组的最大绝对差和。数组的绝对差和是指两个长度相同的数组，对应位置的数值的差的绝对值，然后求和。例如：数组$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$