题解 | #时间序列#

题目链接

时间序列

题目描述

在一次高纬度时空实验中，科学家捕获了两段来自不同宇宙的时间序列信号，分别记为序列 $A$ 和序列 $B$ 。为了分析这两段信号的潜在关联，需要找到它们之间“共鸣度”最高的子序列对。

子序列 (Subsequence)：从一个序列中删除任意数量（可以为零）的元素，保持剩下元素的相对顺序不变，所得到的新序列。例如， $ace$ 是 $abcde$ 的一个子序列，但 $aec$ 不是。
共鸣度 (Resonance Score)：对于两个等长的序列，其共鸣度定义为对应位置元素之差的绝对值之和。例如，对于序列 $S_1 = (x_1, x_2)$ 和 $S_2 = (y_1, y_2)$ ，它们的共鸣度为： $|x_1 - y_1| + |x_2 - y_2|$ 。

您的任务是，分别从原始时间序列 $A$ 和 $B$ 中，找出一对长度相同的非空子序列，使得它们的共鸣度最大，并返回这个最大值。

输入描述

第一行: 两个整数 $N$ 和 $M$ ，分别代表序列 $A$ 和序列 $B$ 的长度。 ( $1 \le N, M \le 5000$ )
第二行: $N$ 个整数，代表序列 $A$ 的元素。每个元素的取值范围为 $[-1000, 1000]$ 。
第三行: $M$ 个整数，代表序列 $B$ 的元素。每个元素的取值范围为 $[-1000, 1000]$ 。

输出描述

输出一个整数，表示可找到的最大共鸣度。

示例

示例 1

输入：

3 3
1 3 5
2 4 6

输出：

说明：从 $A$ 中取子序列 $(1, 3)$ ，从 $B$ 中取子序列 $(4, 6)$ 。它们等长，共鸣度为 $|1-4| + |3-6| = 3 + 3 = 6$ 。

示例 2

输入：

2 2
1 2
3 4

输出：

说明：从 $A$ 中取子序列 $(1, 2)$ ，从 $B$ 中取子序列 $(3, 4)$ 。共鸣度为 $|1-3| + |2-4| = 2 + 2 = 4$ 。

解题思路

这是一个典型的最优化问题，可以通过动态规划 (Dynamic Programming, DP) 解决。我们的目标是构建一个递推关系，从子问题的最优解逐步推导出原问题的最优解。

状态定义

我们定义一个二维数组 $dp[i][j]$ ，表示： 从序列 $A$ 的前 $i$ 个元素 ( $A[1..i]$ ) 和序列 $B$ 的前 $j$ 个元素 ( $B[1..j]$ ) 中，选取等长子序列所能得到的最大共鸣度。

状态转移方程

对于 $dp[i][j]$ 的计算，我们考虑 $A$ 的第 $i$ 个元素 $A[i]$ 和 $B$ 的第 $j$ 个元素 $B[j]$ 的选择情况：

不选择 $A[i]$ ：最大共鸣度取决于在 $A[1..i-1]$ 和 $B[1..j]$ 中能找到的最优解。此时， $dp[i][j]$ 的一个候选值是 $dp[i-1][j]$ 。
不选择 $B[j]$ ：最大共鸣度取决于在 $A[1..i]$ 和 $B[1..j-1]$ 中能找到的最优解。此时， $dp[i][j]$ 的一个候选值是 $dp[i][j-1]$ 。
同时选择 $A[i]$ 和 $B[j]$ ：我们将 $A[i]$ 和 $B[j]$ 进行配对，作为子序列对的最后一组元素。这对元素贡献了 $|A[i] - B[j]|$ 的共鸣度。在此基础上，我们需要加上从 $A[1..i-1]$ 和 $B[1..j-1]$ 中选取子序列所能得到的最大共鸣度，即 $dp[i-1][j-1]$ 。所以，这种情况下的总共鸣度为 $dp[i-1][j-1] + |A[i] - B[j]|$ 。

$dp[i][j]$ 的值应为以上三种情况的最大值。因此，状态转移方程为： $dp[i][j] = \max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + |A[i] - B[j]|)$

初始化

当任意一个序列的长度为 0 时（即 $i=0$ 或 $j=0$ ），无法构成非空子序列对，共鸣度为 0。因此，我们将 DP 表的第一行和第一列全部初始化为 0。 $dp[i][0] = 0$ for $0 \le i \le N$ $dp[0][j] = 0$ for $0 \le j \le M$

最终答案

根据状态定义，遍历完所有元素后， $dp[N][M]$ 即为从整个序列 $A$ 和 $B$ 中选取子序列所能得到的最大共鸣度，也就是题目的最终答案。

空间优化

注意到 $dp[i][j]$ 的计算只依赖于第 $i$ 行和第 $i-1$ 行的数据。因此，我们可以使用滚动数组的思想，将二维 DP 表压缩成一维，从而将空间复杂度从 $O(N \cdot M)$ 优化到 $O(\min(N, M))$ 。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    vector<int> b(m);
    for (int i = 0; i < m; ++i) {
        cin >> b[i];
    }

    // 空间优化：dp[j] 表示 dp[i][j]
    // 确保 dp 数组是基于较短的序列长度，以优化空间
    if (n < m) {
        swap(n, m);
        swap(a, b);
    }

    vector<long long> dp(m + 1, 0);

    for (int i = 1; i <= n; ++i) {
        long long prev_diag = 0; // 存储 dp[i-1][j-1] 的值
        for (int j = 1; j <= m; ++j) {
            long long temp = dp[j]; // 存储 dp[i-1][j] 的值
            long long option1 = dp[j]; // 不选 a[i-1]，对应 dp[i-1][j]
            long long option2 = dp[j - 1]; // 不选 b[j-1]，对应 dp[i][j-1]
            long long option3 = prev_diag + abs(a[i - 1] - b[j - 1]);
            
            dp[j] = max({option1, option2, option3});
            prev_diag = temp;
        }
    }

    cout << dp[m] << endl;

    return 0;
}

import java.util.Scanner;
import java.lang.Math;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        int[] a = new int[n];
        for (int i = 0; i < n; ++i) {
            a[i] = sc.nextInt();
        }

        int[] b = new int[m];
        for (int i = 0; i < m; ++i) {
            b[i] = sc.nextInt();
        }
        
        // 确保 b 是较短的序列以优化空间
        if (n < m) {
            int tempN = n;
            n = m;
            m = tempN;
            int[] tempArr = a;
            a = b;
            b = tempArr;
        }

        long[] dp = new long[m + 1];

        for (int i = 1; i <= n; ++i) {
            long prevDiag = 0; // 存储 dp[i-1][j-1]
            for (int j = 1; j <= m; ++j) {
                long temp = dp[j]; // 存储 dp[i-1][j]
                
                long option1 = dp[j]; // 不选 a[i-1]
                long option2 = dp[j - 1]; // 不选 b[j-1]
                long option3 = prevDiag + Math.abs(a[i - 1] - b[j - 1]);
                
                dp[j] = Math.max(option1, Math.max(option2, option3));
                prevDiag = temp;
            }
        }

        System.out.println(dp[m]);
    }
}

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

    # 确保 b 是较短的序列以优化空间
    if n < m:
        n, m = m, n
        a, b = b, a

    dp = [0] * (m + 1)

    for i in range(1, n + 1):
        prev_diag = 0  # 存储 dp[i-1][j-1]
        for j in range(1, m + 1):
            temp = dp[j]  # 存储 dp[i-1][j]
            
            option1 = dp[j]  # 不选 a[i-1]
            option2 = dp[j - 1]  # 不选 b[j-1]
            option3 = prev_diag + abs(a[i - 1] - b[j - 1])
            
            dp[j] = max(option1, option2, option3)
            prev_diag = temp

    print(dp[m])

solve()

算法及复杂度

算法：动态规划 (DP)
时间复杂度： $O(N \cdot M)$ - 其中 $N$ 和 $M$ 分别是两个序列的长度。
空间复杂度： $O(\min(N, M))$ - 采用滚动数组进行空间优化后。