朴素版本时间复杂度n^3(最坏情况)会在11/13的测试TLE

import java.util.*;

public class Main {
    static final int N = 3010;
    static int[] a = new int[N], b = new int[N];
    static int[][] f = new int[N][N];
    static int n;

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

        n = Integer.parseInt(sc.nextLine());
        String[] s = sc.nextLine().split(" ");
        for (int i = 1; i <= n; i++) a[i] = Integer.parseInt(s[i - 1]);
        s = sc.nextLine().split(" ");
        for (int i = 1; i <= n; i++) b[i] = Integer.parseInt(s[i - 1]);
        /**
        * f[i][j]表示a的前i个字母和b的前j个字母并且以b[j]结尾的最长公共上升子序列
        * 
        *
        */
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) {
                f[i][j] = f[i - 1][j];//当a[i]不是子序列的一部分时
                if (a[i] == b[j]) {//只有当a[i] = b[j]时才会有公共子序列, 保证公共序列
                    f[i][j] = Math.max(f[i][j], 1);//只有自身时
                    for (int k = 1; k < j; k++)//从1枚举到j - 1
                        if (b[k] < b[j])//保证上升序列
                            f[i][j] = Math.max(f[i][j], f[i - 1][k] + 1);//从f[i - 1][k] + 1, 该1就是a[i] b[j]
                }
            }

        int res = 0;
        for (int i = 1; i <= n; i++) res = Math.max(res, f[n][i]);

        System.out.println(res);
    }
}

优化版本

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

public class Main {
    static final int N = 3010;
    static int[] a = new int[N], b = new int[N];
    static int[][] f = new int[N][N];
    static int n;

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

        n = Integer.parseInt(sc.nextLine());
        String[] s = sc.nextLine().split(" ");
        for (int i = 1; i <= n; i++) a[i] = Integer.parseInt(s[i - 1]);
        s = sc.nextLine().split(" ");
        for (int i = 1; i <= n; i++) b[i] = Integer.parseInt(s[i - 1]);

        for (int i = 1; i <= n; i++) {
            int maxv = 1;//使用变量保存每一行 前面j个数的最大值，初始化为1是在枚举长度为1的情况(只有自身)
            for (int j = 1; j <= n; j++) {
                f[i][j] = f[i - 1][j];////当a[i]不是子序列的一部分时
                if (a[i] == b[j]) f[i][j] = Math.max(f[i][j], maxv);//相等时取最大值即可
                if (b[j] < a[i]) maxv = Math.max(maxv, f[i - 1][j] + 1);//更新(维护)maxv(前缀最大值)
            }
        }
        int res = 0;
        for (int i = 1; i <= n; i++) res = Math.max(res, f[n][i]);

        System.out.println(res);
    }
}