题目链接https://www.acwing.com/problem/content/897/

一、求最长上升子序列长度

1、朴素版本 O(n2)

f[i]可以看作以num[i]为末尾的最长子序列的长度集合，现在要求集合中的最大值。f[i]的分类是由此序列的倒数第二个数num[j]来划分的，f[i]可以用f[j]+1来表示，此处j是这个上升子序列的倒数第二个值，用循环来求

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] num = new int[1005];
        int[] f = new int[1005];
        for(int i = 1; i <= n; i++) num[i] = in.nextInt();
        for(int i = 1; i <= n; i++) {
            f[i] = 1;
            for(int j = 1; j <= n; j++) {
                if(num[i] > num[j]) {
                    f[i] = Math.max(f[i],f[j] + 1);
                }
            }
        }
        int res = 0;
        for(int i = 1; i<= n;i++) {
            res = Math.max(f[i],res);
        }
        System.out.print(res);
    }
}

2、优化版本O(nlogn)

这个版本比起DP更像贪心

时间复杂度的计算

二分的时间复杂度是logn，循环n次，故为nlogn :::info 假使总共有n个元素，那么二分后每次查找的区间大小就是n，n/2，n/4，…，n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数。
最坏的情况是K次二分之后,每个区间的大小为1,找到想要的元素
令n/2^k=1，
可得k=log2n,（是以2为底，n的对数），所以时间复杂度可以表示O()=O(logn). :::

代码

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] q = new int[n+5];
        int[] a = new int[n+5];
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
        }
        int len = 0;
        q[0] = (int) -2e9;
        for (int i = 0; i <= n; i++) {
            int l = 0,r = len;
            while (l < r) {
                int mid = l + r +1 >> 1;
                if(q[mid] < a[i]) l = mid;
                else r = mid - 1;
            }
            q[l + 1] = a[i];
            len = Math.max(len, r + 1);
        }
        System.out.println(len);
    }
}

二、打印最长上升子序列(倒序输出)

打印最长子序列的时候可以用g[i]数组来表示每个以num[i]结尾的最长上升子序列的上一个数在num数组中的下标。
以输入样例为例

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] num = new int[1005];
        int[] f = new int[1005];
        int[] g = new int[1005];
        for(int i = 1; i <= n; i++) num[i] = in.nextInt();
        for(int i = 1; i <= n; i++) {
            f[i] = 1;
            g[i] = 0;
            for(int j = 1; j < i; j++) {
                if(num[i] > num[j]) {
                    if(f[i] < f[j] + 1){
                        f[i] = f[j] + 1;
                        // g[i]存的是以i结尾的序列的倒数第二个数在num中的下标
                        g[i] = j;
                    }
                }
            }
        }
        // 这个循环取出最大值
        int k = 1;
        for(int i = 1; i<= n;i++) {
            if (f[k] < f[i]) k = i;
        }
        System.out.println(f[k]);
        // 这个循环取出路径,输出为倒序
        for (int i = 0, len = f[k]; i < len; i++) {
            System.out.print(num[k]+" ");
            k = g[k];
        }
    }
}