算法学习-LIS最长上升子序列模板（JAVA实现）

本文最后更新于：January 27, 2022 pm

纸上得来终觉浅，绝知此事要躬行。路漫漫其修远兮，吾将上下而求索！知识是经过历史的巨人沉淀下来的，别总想着自己能够快速学会，多花点时间去看看，也许会发现些不同的东西。你能快速学会的、觉得简单的东西，对于别人来说也是一样的。人外有人，天外有天。当努力到达了一定的程度，幸运自会与你不期而遇。

目录

计算最长上升子序列的长度。

动态规划

时间复杂度：O(n*n)

数组 d[ i ] 表示前 i 个数以 A[ i ] 结尾的最长上升子序列长度。

例如：求 2 7 1 5 6 4 3 8 9 的最长上升子序列。

  • 前1个数 d(1)=1 子序列为2；

  • 前2个数 7前面有2小于7 d(2)=d(1)+1=2 子序列为2 7

  • 前3个数 在1前面没有比1更小的，1自身组成长度为1的子序列 d(3)=1 子序列为1

  • 前4个数 5前面有2小于5 d(4)=d(1)+1=2 子序列为2 5

  • 前5个数 6前面有2 5小于6 d(5)=d(4)+1=3 子序列为2 5 6

  • 前6个数 4前面有2小于4 d(6)=d(1)+1=2 子序列为2 4

  • 前7个数 3前面有2小于3 d(3)=d(1)+1=2 子序列为2 3

  • 前8个数 8前面有2 5 6小于8 d(8)=d(5)+1=4 子序列为2 5 6 8（d[5]>d[6]）

  • 前9个数 9前面有2 5 6 8小于9 d(9)=d(8)+1=5 子序列为2 5 6 8 9（前面中d[8]最大）

最后求d数组中的最大值即可。

状态：

F [ i ] = max { F [ j ] + 1 ，F [ i ] } (1 <= j < i，A[ j ] < A[ i ])

当然了，开始每一个数都是长度为1的，F [ i ] = 1 (1 <= i <= n)

代码实现

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
import java.io.*;
import java.text.SimpleDateFormat;
import java.util.*;


/**
 * @Author DragonOne
 * @Date 2021/12/5 21:27
 * @墨水记忆 www.tothefor.com
 */
public class Main {
    public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    public static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
    public static Scanner sc = new Scanner(System.in);

    public static int maxd = 10000+7;
    public static int INF = 0x3f3f3f3f;
    public static int mod = 998244353;
    public static int[] a = new int[maxd];
    public static int[] f = new int[maxd];
    public static int  ans = -1*INF;

    public static void main(String[] args) throws Exception {
        int n = nextInt();
        for(int i=1;i<=n;++i){
            a[i]=nextInt();
            f[i]=1;
        }
        for(int i=1; i<=n; i++){
            for(int j=1; j<i; j++){
                if(a[j] < a[i]) f[i] = Math.max(f[i], f[j]+1);
            }
        }
        for(int i=1; i<=n; i++){
            ans = Math.max(ans, f[i]);
        }
        System.out.println(ans);

        closeAll();
    }

    public static void cinInit(){
        cin.wordChars('a', 'z');
        cin.wordChars('A', 'Z');
        cin.wordChars(128 + 32, 255);
        cin.whitespaceChars(0, ' ');
        cin.commentChar('/');
        cin.quoteChar('"');
        cin.quoteChar('\'');
        cin.parseNumbers();
    }
    public static int nextInt() throws Exception {
        cin.nextToken();
        return (int) cin.nval;
    }
    public static long nextLong() throws Exception {
        cin.nextToken();
        return (long) cin.nval;
    }
    public static double nextDouble() throws Exception {
        cin.nextToken();
        return cin.nval;
    }
    public static String nextString() throws Exception {
        cin.nextToken();
        return cin.sval;
    }
    public static void closeAll() throws Exception {
        cout.close();
        in.close();
        out.close();
    }
}

输入输出：

1
2
3
4
5
6
//输入
6
1 5 2 4 6 9

//输出  
5

二分

时间复杂度：O(n*logn)

新建一个 low 数组，low [ i ]表示长度为i的LIS结尾元素的最小值。对于一个上升子序列，显然其结尾元素越小，越有利于在后面接其他的元素，也就越可能变得更长。因此，我们只需要维护 low 数组，对于每一个a[ i ]，如果a[ i ] > low [当前最长的LIS长度]，就把 a [ i ]接到当前最长的LIS后面，即low [++当前最长的LIS长度] = a [ i ]。 否则，就用 a [ i ] 去更新 low 数组（在 low 数组中找到第一个大于等于a [ i ] 的位置。）。

具体更新方法：在low数组中找到第一个大于等于a [ i ]的元素low [ j ]，用a [ i ]去更新 low [ j ]。如果从头到尾扫一遍 low 数组的话，时间复杂度仍是O(n^2)。我们注意到 low 数组内部一定是单调不降的，所有我们可以二分 low 数组，找出第一个大于等于a[ i ]的元素。

代码实现

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
import java.io.*;
import java.math.BigInteger;
import java.util.*;


/**
 * @Author DragonOne
 * @Date 2021/12/5 21:27
 * @墨水记忆 www.tothefor.com
 */
public class Main {
    public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    public static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
    public static Scanner sc = new Scanner(System.in);

    public static int maxd = 100000+7;
    public static int INF = 0x3f3f3f3f;
    public static int mod = 998244353;
    public static int[] low = new int[maxd];
    public static int[] a = new int[maxd];

    public static int bin_query(int[] arr,int r,int x){ //在arr数组中找第一个大于等于x的位置
        int l = 1;
        while(l<=r){
            int mid = (r+l)/2;
            if(arr[mid]<=x) l=mid+1;
            else r = mid-1;
        }
        return l;
    }

    public static void main(String[] args) throws Exception {

        int n = nextInt();
        for(int i=1;i<=n;++i){
            a[i] = nextInt();
            low[i] = INF;
        }
        low[1]=a[1];
        int ans = 1; //初始化长度为1
        for(int i=1;i<=n;++i){
            if(a[i]>low[ans]) low[++ans] = a[i];
            else{
                int ind = bin_query(low,ans,a[i]);
                low[ind] = a[i];
            }
        }
        System.out.println(ans);

        closeAll();
    }

    public static void cinInit(){
        cin.wordChars('a', 'z');
        cin.wordChars('A', 'Z');
        cin.wordChars(128 + 32, 255);
        cin.whitespaceChars(0, ' ');
        cin.commentChar('/');
        cin.quoteChar('"');
        cin.quoteChar('\'');
        cin.parseNumbers(); //可单独使用来还原数字
    }

    public static int log(int x){ //log方法是以2为底,求x的对数。java自带的log是以e为底的
        return (int) (Math.log(x)/Math.log(2));
    }

    public static int nextInt() throws Exception{
        cin.nextToken();
        return (int) cin.nval;
    }
    public static long nextLong() throws Exception{
        cin.nextToken();
        return (long) cin.nval;
    }
    public static double nextDouble() throws Exception{
        cin.nextToken();
        return cin.nval;
    }
    public static String nextString() throws Exception{
        cin.nextToken();
        return cin.sval;
    }
    public static void closeAll() throws Exception {
        cout.close();
        in.close();
        out.close();
    }

}

输入输出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//输入
10
2
3
4
5
6
7
8
9
10
1
    
//输出    
9