#yyds干货盘点# 动态规划专题：最长上升子序列(一)

1.简述：

描述

给定一个长度为 n 的数组 arr，求它的最长严格上升子序列的长度。

所谓子序列，指一个数组删掉一些数（也可以不删）之后，形成的新数组。例如 [1,5,3,7,3] 数组，其子序列有：[1,3,3]、[7] 等。但 [1,6]、[1,3,5] 则不是它的子序列。

我们定义一个序列是 严格上升 的，当且仅当该序列不存在两个下标  和  满足  且 。

数据范围：  , 

要求：时间复杂度 ， 空间复杂度 

输入描述：

第一行输入一个正整数 n ，表示数组的长度 

第二行输入 n 个整数表示数组的每个元素。

输出描述：

输出最长严格上升子序列的长度

示例1

输入：

7
6 3 1 5 2 3 7

输出：

4

说明：

该数组最长上升子序列为 [1,2,3,7] ，长度为4

2.代码实现：

import java.util.Scanner;
import java.util.LinkedList;
import java.util.List;

public class Main{

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

        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        // dp记录<上升序列的末尾数字, 该序列长度>，按长度排序
        // <num, length>
        List<DP> dp = new LinkedList<>();

        dp.add(0, new DP(a[0], 1));

        for (int i = 1; i < n; i++) {
            // 前面记录的dp中是否有比a[i]小的数字
            boolean hasSmall = false;
            for (int j = 0; j < dp.size(); j++) {
                if (dp.get(j).num < a[i]) {
                    // 前面dp中有比a[i]小的数字，并且dp是按长度排序的，此处一定是最大子序列
                    int length = dp.get(j).length + 1;    // 序列长度+1
                    for (int k = 0; k < dp.size(); k++) {
                        // 插入dp时，按照length长度从大到小顺序插入
                        if (!(dp.get(k).length > length)) {
                            dp.add(k, new DP(a[i], length));
                            break;
                        }
                    }
                    hasSmall = true;
                    break;
                }
            }

            // 前面dp中没有比a[i]小的数字，把a[i]记为长度1
            if (!hasSmall) {
                dp.add(dp.size(), new DP(a[i], 1));
            }
        }

        System.out.println(dp.get(0).length);
    }

    public static class DP {
        public int num;
        public int length;

        public DP(int num, int length) {
            this.num = num;
            this.length = length;
        }
    }
}