最长上升子序列（2）

链接：https://www.acwing.com/problem/content/898/

来源：ACWing 算法基础课

题目描述

给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式

第一行包含整数 N。

第二行包含 N 个整数，表示完整序列。

输出格式

输出一个整数，表示最大长度。

数据范围

1≤N≤100000
−109≤数列中的数≤109

输入样例：

1
2
7
3 1 2 1 8 5 6

输出样例：

1
4

算法描述

本题数据范围较大，不宜使用双层for循环+DP的方法进行编写。

则采用优化进阶版的二分算法来进行编写

状态表示

找到相应的上升子序列长度结尾的最小值，每次都这样找的话就可以找到一个呈现递增状态的数组，递增状态的属性满足了使用二分的基本规则

状态计算（集合划分）

  1. 使用dp[len]来记录当0~len各个长度下的最小值

  2. 当a[i]>dp[len]中的所有值时，len的长度要增加

  3. 更新a[i]成为1~len的某个长度下的最小值

笔者代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.util.Scanner;
import java.util.Stack;

/**
 * @author 白依
 * 思路整理结果:二分小于某个数的最大的数
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int N = 100010;
        int[] arr = new int[N];
        int[] q = new int[N];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }

        int len = 0;
         q[0] = Integer.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            int l=0,r=len;
            while (l<r){
                int mid = 1+l+r>>1;
                if(q[mid]<arr[i]){
                    l = mid;
                } else{
                    r=mid-1;
                }
            }
            len = Math.max(len,r+1);
            q[r+1] = arr[i];
        }
        System.out.println(len);
    }
}