1.最长上升子序列
https://www.acwing.com/activity/content/problem/content/1003/

import java.util.*;

public class Main {
    static int N = 1010;
    static int[] a = new int[N];
    static int[] f = new int[N];//以a[i]为结尾的上升子序列的长度的最大值（属性）

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 1;i <= n;i ++) a[i] = sc.nextInt();

        for (int i = 1;i <= n;i ++) {
            f[i] = 1;
            for (int j = 1;j < i;j ++) {
                //对所有前面已经确定好的f进行比较取最大值，然后+1，即为以a[i]最长上升子序列的最大值
                if (a[j] < a[i]) //保证上升
                    f[i] = Math.max(f[i],f[j] + 1);
            }
        }

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

        System.out.print(res);
    }
}

2.最长公共子序列（不要求连续）
https://www.acwing.com/activity/content/problem/content/1005/

import java.util.*;

public class Main {
    static int N = 1010;
    static int n,m;
    static int[] a = new int[N];
    static int[] b = new int[N];
    static int[][] f = new int[N][N];//以前i个字母和前j个字母组成的公共子序列的最大值（属性）

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        String s1 = sc.next();
        String s2 = sc.next();
        for (int i = 1;i <= n;i ++) a[i] = s1.charAt(i-1);
        for (int i = 1;i <= m;i ++) b[i] = s2.charAt(i-1);

        for (int i = 1;i <= n;i ++) {
            for (int j = 1;j <= m;j ++) {
                f[i][j] = Math.max(f[i-1][j],f[i][j-1]);//不包含a[i]/不包含b[j]
                if (a[i] == b[j]) //a[i] = b[j]是同时选的前提
                    f[i][j] = Math.max(f[i][j],f[i-1][j-1] + 1);
            }
        }
        System.out.print(f[n][m]);
    }
}

最长连续公共子序列
https://www.acwing.com/activity/content/problem/content/8792/
线性dp

import java.util.*;

public class Main {
    static int N = 110;
    static char[] a = new char[N];
    static char[] b = new char[N];
    static int[][] f = new int[N][N];//s1和s2分别以i,j结尾的子串，二者后缀的最大匹配长度
    static int res;
    static int l,r;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s1 = sc.next();
        String s2 = sc.next();
        for (int i = 1;i <= s1.length();i ++) a[i] = s1.charAt(i - 1);
        for (int i = 1;i <= s2.length();i ++) b[i] = s2.charAt(i - 1);
        int n = s1.length();
        int m = s2.length();

        int l = 0,r = 0;
        int res = 0;
        for (int i = 1;i <= n;i ++) {
            for (int j = 1;j <= m;j ++) {
                if (a[i] == b[j]) f[i][j] = f[i-1][j-1] + 1;
                else f[i][j] = 0;

                if (res <= f[i][j]) {
                    res = f[i][j];
                    r = i;
                    l = i - res + 1;
                }
            }
        }
        System.out.println(res);
        for (int i = l;i <= r;i ++) 
            System.out.print(a[i]);
    }
}

暴力枚举

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String a = sc.next();
        String b = sc.next();

        String res = "";
        //要求最长连续公共子序列，所以要倒着求，从长度最大的子序列开始找，找到就可以break
        for (int len = Math.min(a.length(),b.length());len > 0;len --) { //枚举每一种长度
            //题目要求输出最后一个，所以从末尾开始遍历
            for (int i = a.length() - len;i >= 0;i --) { //枚举每一种长度为len的在a中的子串
                for (int j = b.length() - len;j >= 0;j --) { //枚举每一种长度为len的在b中的子串，确认是否与a中选出来的匹配
                    String s1 = a.substring(i,i + len);//substring左闭右开
                    String s2 = b.substring(j,j + len);
                    if (s1.equals(s2)) {
                        res = s1;
                        break;
                    }
                }
                if (res.length() != 0) break;
            }
            if (res.length() != 0) break;
        }

        System.out.println(res.length());
        System.out.println(res);
    }
}

最长公共上升子序列
https://www.acwing.com/activity/content/problem/content/1266/

//因为a和b是等价的,所以用a去解决公共子序列问题,用b去解决上升子序列问题
import java.util.*;

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for (int i = 1;i <= n;i ++) a[i] = sc.nextInt();
        for (int i = 1;i <= n;i ++) b[i] = sc.nextInt();
        //枚举所有情况
        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]的情况
                    f[i][j] = 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 res = 0;
        for (int i = 1;i <= n;i ++)
            res = Math.max(res,f[n][i]);

        System.out.println(res);
    }
}