有个问题把自己绕进去了 是不是&&为什么“最长公共上升子序列 $\neq$ 最长公共子序列的最长上升子序列” 一时脑抽举不出反例 谢谢谢

朴素DP $O(n^3)$

1. $f(i,j)$表示“只考虑$a$数组的前$i$个和$b$数组的前$j$个，且以$b_j$结尾的选法集合”，属性：公共上升子序列长度$Max$
2. 状态计算，因为定义“以$b_j$结尾”，所以对每个$a_i$，枚举每个$b_j$结尾的情况，讨论$a_i$的是否可选
   • $a_i \neq b_j$，此时$a_i$不能加入以$b_j$结尾的序列，序列最大长度为$f(i,j) = f(i-1,j)$
   • $a_i = b_j$，此时$a_i$能加入以$b_j$结尾的序列，但所求的是最长升序子序列，所以要进一步讨论
     • 先考虑这个序列仅有$a_i$一个元素的情况，显然序列长度为1，即$f(i,j)=1$
     • 再考虑之前的数是否“存在以$b_k$结尾且$b_k < b_j$的序列且序列长度大于当前已记录的最大长$f(i,j)$”的情况，如果有则更新$f(i,j)$到最大值，即$f(i,j)=max(f(i,j),f(i-1,k)+1)$
   • 综上，$f(i,j) = max(1, f(i-1,k)+1), 1 \leq k \leq j-1$
   • 就是考虑当前的是否共有，不共有则状态从前一位转移，共有则考虑能否与之前已有的上升序列组成更长的序列，不能则自成一个序列

代码 $O(n^3)$

import java.util.*;
import java.lang.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    static int n;
    static int[][] f = new int[3010][3010];
    static int[] a = new int[3010], b = new int[3010];

    public static void main(String[] args) {
        n = scanner.nextInt();
        for (int i = 1; i <= n; i++) {
            a[i] = scanner.nextInt();
        }
        for (int i = 1; i <= n; i++) {
            b[i] = scanner.nextInt();
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                f[i][j] = f[i - 1][j];  // 不可选则状态从上一位转移
                if (a[i] == b[j]) {  // 可选
                    f[i][j] = 1;  // 最起码可以自成一个序列 长度为1
                    for (int k = 1; k < j; k++) {  // 遍历之前的数 如果可以接到其它序列组成更长的序列 就更新选法
                        if (b[k] < b[j]) {  // 条件是上升序列
                            f[i][j] = Math.max(f[i][j], f[i - 1][k] + 1);
                        }
                    }
                }
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans = Math.max(ans, f[n][i]);  // 最终的序列不一定以b[i]结尾 需要遍历所有情况
        }
        System.out.println(ans);
    }
}

时间优化 $O(n^2)$

对于第三个循环结构

for (int k = 1; k < j; k++) {
    if (b[k] < b[j]) {
        f[i][j] = Math.max(f[i][j], f[i - 1][k] + 1);
    }
}

无非是求，“只考虑$a_1 \sim a_{i-1}$和$b_1 \sim b_{j-1}$”的旧序列中能与$a_i$（$b_j$）组成“更长的公共上升序列”的最大旧序列长度
第三个循环结构的遍历范围是第二个循环的子集，每次遍历取最大值的操作是重复冗余的，因此可以合并两个循环，用一个变量maxv存当前最大的$f(i-1,k)$，后续只需与maxv比较即可

代码 $O(n^2)$

import java.util.*;
import java.lang.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    static int n;
    static int[][] f = new int[3010][3010];
    static int[] a = new int[3010], b = new int[3010];

    public static void main(String[] args) {
        n = scanner.nextInt();
        for (int i = 1; i <= n; i++) {
            a[i] = scanner.nextInt();
        }
        for (int i = 1; i <= n; i++) {
            b[i] = scanner.nextInt();
        }
        for (int i = 1; i <= n; i++) {
            int maxv = 0;  // 记录f(i-1, 1···j-1)的最大值
            for (int j = 1; j <= n; j++) {
                f[i][j] = f[i - 1][j];  // 不选
                if (a[i] == b[j]) {  // 可选
                    f[i][j] = Math.max(f[i][j], maxv + 1);
                } else if (b[j] < a[i]) {  // 考虑f(i-1,j) 取可接受a[i]的旧序列长度最大值
                    maxv = Math.max(maxv, f[i - 1][j]);
                }
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans = Math.max(ans, f[n][i]);
        }
        System.out.println(ans);
    }
}

空间优化 到一维

$f(i, j)$的状态只与$f(i-1, j)$有关，改成一维数组，回滚即可

import java.util.*;
import java.lang.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    static int n;
    static int[] f = new int[3010];
    static int[] a = new int[3010], b = new int[3010];

    public static void main(String[] args) {
        n = scanner.nextInt();
        for (int i = 1; i <= n; i++) {
            a[i] = scanner.nextInt();
        }
        for (int i = 1; i <= n; i++) {
            b[i] = scanner.nextInt();
        }
        for (int i = 1; i <= n; i++) {
            int maxv = 0;
            for (int j = 1; j <= n; j++) {
                if (a[i] == b[j]) {
                    f[j] = Math.max(f[j], maxv + 1);
                } else if (b[j] < a[i]) {
                    maxv = Math.max(maxv, f[j]);
                }
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans = Math.max(ans, f[i]);
        }
        System.out.println(ans);
    }
}