华为 · 动态规划 · 算法编程题
华为 动态规划 N ≤ 500 时限 3 秒 / 256 MB

题目描述

在一次高纬度时空实验中，科学家捕获了两段来自不同宇宙的时间序列信号，分别记为序列 A 和序列 B 。
为了分析这两段信号的潜在关联，需要找到它们之间“共鸣度”最高的子序列对。
1. 子序列 (Subsequence) ：从一个序列中删除任意数量（可以为零）的元素，保持剩下元素的相对顺序不变，所得到的新序列。例如， [2, 5] 是 [1, 2, 3, 4, 5] 的一个子序列，但 [5, 2] 不是。
2. 共鸣度 (Resonance Score) ：对于两个等长的序列，其共鸣度定义为对应位置元素之差的绝对值之和。
例如，对于序列 X = [x_1, x_2] 和 Y = [y_1, y_2] ，它们的共鸣度为：
S = |x_1 - y_1| + |x_2 - y_2|
您的任务是，分别从原始时间序列 A 和 B 中，找出一对长度相同的非空子序列，使得它们的共鸣度最大，并返回这个最大值。

输入输出

输入描述
1. 第一行 : 两个整数 N 和 M ，分别代表序列 A 和序列 B 的长度。
1 ≤ N, M ≤ 500
2. 第二行 : N 个整数，代表序列 A 的元素。
每个元素的取值范围为 [-1000, 100] 。
3. 第三行 : M 个整数，代表序列 B 的元素。
每个元素的取值范围为 [-1000, 100] 。
输出描述
输出一个整数，表示可找到的最大共鸣度。

样例共 2 组

样例 1
输入
3 3
1 3 5
2 4 6
输出
6
样例 2
输入
2 2
1 2
3 4
输出
4

算法解析依据充分

考点：动态规划

数据规模 N ≤ 500 ｜ 限制 3 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：N ≤ 500，M ≤ 500
  • 复杂度门槛：允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
  • 源站时限：3 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：动态规划

本题切入点

两序列各取等长子序列使 Σ|差| 最大：dp[i][j] = 以 A[i]、B[j] 配对结尾时的最大共鸣度，转移取「配对/跳过」的最大值，N,M≤500 时 O(NM) 可行。

把问题拆成子问题，用状态表示「已处理到哪儿」，靠转移方程递推。

思路框架（动态规划 通法 · 非本题专属）

  1. 定义状态：dp[i] / dp[i][j] 表示什么（这是最关键的一步，状态定义错就全错）。
  2. 写转移方程：当前状态由哪些更小的状态推来。
  3. 确定初始条件与遍历顺序（保证用到的状态已算好）。
  4. 确定答案取哪个状态；数值大时全程取模。

实现要点：一般是「先枚举阶段，再枚举状态，最后枚举决策」三层循环；空间大时可滚动数组优化。

复杂度：时间 O(状态数 × 转移代价) ｜ 空间 O(状态数)

该范式的通法易错点

  • 状态定义不完整（漏了必要维度），导致子问题之间有后效性。
  • 初始化写错（尤其「恰好」与「至多」的初值差别）。
  • 遍历顺序与依赖方向不一致。

对照本题

  • 数据规模 N ≤ 500，允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。

样例

样例 1

  • 输入：3 3 / 1 3 5 / 2 4 6
  • 输出：6

样例 2

  • 输入：2 2 / 1 2 / 3 4
  • 输出：4

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：2025年秋招-华为-11月12号开发岗。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解