时间序列

题目分析

给定两个序列 A（长度 n）和 B（长度 m），分别从 A 和 B 中选出等长的非空子序列（保持元素在原序列中的相对顺序），定义"共振度"为对应位置元素之差的绝对值之和。求最大共振度。

思路

动态规划（LCS 变种）

本题是经典最长公共子序列（LCS）的变种。LCS 是求最长匹配，而本题是求最大代价匹配——每匹配一对 $(a_i, b_j)$ ，贡献 $|a_i - b_j|$ ，目标是最大化总贡献。

定义 $dp[i][j]$ 为只考虑 A 的前 $i$ 个元素和 B 的前 $j$ 个元素时，能获得的最大共振度。转移方程：

$ $dp[i][j] = \max\begin{cases} dp[i-1][j] & \text{不选 } a_i \\ dp[i][j-1] & \text{不选 } b_j \\ dp[i-1][j-1] + |a_i - b_j| & \text{匹配 } a_i \text{ 和 } b_j \end{cases}$ $

初始值 $dp[0][j] = dp[i][0] = 0$ ，答案为 $dp[n][m]$ 。

这与 LCS 的转移结构完全一致，只是把"长度+1"替换为"累加绝对值差"。由于每一行只依赖上一行，可以用滚动数组将空间优化到 $O(m)$ 。

以样例 1 为例验证： A=[1,3,5], B=[2,4,6]。选择子序列 A'=[1,3], B'=[4,6]，共振度 $= |1-4| + |3-6| = 3 + 3 = 6$ ，即为最大值。

代码

C++
Java
Python3
JavaScript

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

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    vector<int> a(n), b(m);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    for (int i = 0; i < m; i++) scanf("%d", &b[i]);

    vector<long long> dp(m + 1, 0);
    for (int i = 0; i < n; i++) {
        vector<long long> ndp(m + 1, 0);
        for (int j = 1; j <= m; j++) {
            ndp[j] = max({ndp[j - 1], dp[j],
                          dp[j - 1] + (long long)abs(a[i] - b[j - 1])});
        }
        dp = ndp;
    }
    printf("%lld\n", dp[m]);
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        in.nextToken(); int n = (int) in.nval;
        in.nextToken(); int m = (int) in.nval;
        int[] a = new int[n], b = new int[m];
        for (int i = 0; i < n; i++) { in.nextToken(); a[i] = (int) in.nval; }
        for (int i = 0; i < m; i++) { in.nextToken(); b[i] = (int) in.nval; }

        long[] dp = new long[m + 1];
        for (int i = 0; i < n; i++) {
            long[] ndp = new long[m + 1];
            for (int j = 1; j <= m; j++) {
                ndp[j] = Math.max(Math.max(ndp[j - 1], dp[j]),
                        dp[j - 1] + Math.abs(a[i] - b[j - 1]));
            }
            dp = ndp;
        }
        System.out.println(dp[m]);
    }
}

import sys
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    dp = [0] * (m + 1)
    for i in range(n):
        ndp = [0] * (m + 1)
        for j in range(1, m + 1):
            ndp[j] = max(ndp[j - 1], dp[j], dp[j - 1] + abs(a[i] - b[j - 1]))
        dp = ndp
    print(dp[m])

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const [n, m] = lines[0].split(' ').map(Number);
    const a = lines[1].split(' ').map(Number);
    const b = lines[2].split(' ').map(Number);

    let dp = new Array(m + 1).fill(0);
    for (let i = 0; i < n; i++) {
        const ndp = new Array(m + 1).fill(0);
        for (let j = 1; j <= m; j++) {
            ndp[j] = Math.max(ndp[j - 1], dp[j],
                dp[j - 1] + Math.abs(a[i] - b[j - 1]));
        }
        dp = ndp;
    }
    console.log(dp[m]);
});

复杂度分析

时间复杂度： $O(nm)$ ，双重循环遍历两个序列。
空间复杂度： $O(m)$ ，滚动数组优化后只需一维数组。