题目描述

线性DP

样例

import java.util.*;

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

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

        for (int i = 1; i <= n; i++)
            a[i] = scanner.nextInt();

        for (int i = 1; i <= n; i++) {
            f[i] = 1; // 只有a[i]一个数
            for (int j = 1; j < i; j++)
                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.println(res);
    }
}

输出路径版

import java.util.*;

public class Main {
    static final int N = 1010;
    static int[] a = new int[N];
    static int[] f = new int[N];
    //存储当前数字位置从哪个位置转移过来
    static int[] g = new int[N];

    static int[] t = new int[N];
    static int n;

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

        for (int i = 1; i <= n; i++)
            a[i] = scanner.nextInt();

        for (int i = 1; i <= n; i++) {
            f[i] = 1; // 只有a[i]一个数
            g[i] = 0;// 第i个数是从哪里转移过来的
            //这里默认初始化只要一个元素 所以只能是从第0元素转移过来
            for (int j = 1; j < i; j++){
                if (a[j] < a[i]){
                  if(f[i] < f[j] + 1){//从j更新过来的
                     f[i] = f[j] + 1;
                     g[i] = j;//第i个元素是从第j个元素转移过来的 
                   }  
                }
            }
        }

        int k=1;
        for (int i = 1; i <= n; i ++ ){ //遍历所有以i结尾的
           if(f[k] < f[i]){
               k=i;// 最大长度所在的下标
           }
        }

        System.out.println(f[k]);
        int res = f[k];

        for(int i = 0,len = f[k]; i < len; i++){//f[k]为最长上升子序列长度 
           t[i] = a[k];// 这里先保存 因为g数组只保存了从哪一个状态 前一个节点
           k = g[k];//前一个节点
        }

        for(int i = res - 1; i >= 0; i--){
            System.out.print(t[i] + " ");
        }
    }
}