题目描述

熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。

小沐沐先让奶牛研究了最长上升子序列，再让他们研究了最长公共子序列，现在又让他们研究最长公共上升子序列了。

小沐沐说，对于两个数列 A
和 B

，如果它们都包含一段位置不一定连续的数，且数值是严格递增的，那么称这一段数是两个数列的公共上升子序列，而所有的公共上升子序列中最长的就是最长公共上升子序列了。

奶牛半懂不懂，小沐沐要你来告诉奶牛什么是最长公共上升子序列。

不过，只要告诉奶牛它的长度就可以了。

数列 A
和 B 的长度均不超过 3000。

样例

4
2 2 1 3
2 1 2 3

2

算法1

(动态规划)

时间复杂度

参考文献

Java 代码

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int N = input.nextInt();
        int[] A = new int[N];
        int[] B = new int[N];
        int[][] dp = new int[N + 10][N + 10];
        for (int i = 0; i < N; i++) {
            A[i] = input.nextInt();
        }
        for (int i = 0; i < N; i++) {
            B[i] = input.nextInt();
        }

        // 初始化
        for (int i = 0; i < N; i++) {
            dp[0][i] = 0;
        }

        for (int i = 0; i < N; i++) {
            dp[i][0] = 0;
        }

        for (int i = 1; i <= N; i++) {
            int curMax = Integer.MIN_VALUE;
            for (int j = 1; j <= N; j++) {
                if (A[i - 1] == B[j - 1]) {
                    if (A[i - 1] <= curMax) {
                        dp[i][j] = 1;
                        curMax = A[i - 1];
                        continue;
                    }
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    curMax = A[i - 1];
                } else {
                    // 查看前面是A数列少一位之后更长，还是B数列少一位之后更长，选较长的那个作为此时的长度
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

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