最长上升子序列

利用这个题目好好学习下动态规划，一直对动态规划不太理解。所以这边尽量以通俗易懂的语言将明白。

300最长上升子序列（LeetCode）

题目

1

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例：

1
2
3


输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

说明:

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。

你算法的时间复杂度应该为 O(n2) 。

进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

解题思路：

1、看了上图就很容易理解了，从10开始，长度为1；
2、然后遍历到9,9比10要小，所以长度还是1；
3、接着遍历到2,2比9、10都小，所以长度也是1；
4、当遍历到5的时候，5比前面数组中的2要大，比9、10要小，所以长度更新为2；
5、接着这样比下去。（比如当比较到7的时候，有两个序列的长度都是3，记录长度为就好）

 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


package com.zhoujian.solutions.leetcode;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author zhoujian123@hotmail.com 2018/8/29 16:42
 */
public class LongIncreaseSubsequence {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        String[] s1 = s.split(" ");
        int[] nums = new int[s1.length + 1];
        for (int i = 0; i < s1.length; i++) {
            nums[i]= Integer.parseInt(s1[i]);
        }
        int n = lengthOfLIS(nums);
        System.out.println(n);
    }

    private static int lengthOfLIS(int[] nums) {

        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int len =nums.length,max=0;
        int[] dp = new int[len];
        for (int i = 0; i < len; i++) {
            //将数组初始化为1
            dp[i]=1;
            for (int j = 0; j < i; j++) {
                //如果后面的值大于前面的数字的值，并且dp的长度也大于j之前的值
                if (nums[i] > nums[j] && dp[j]+1 >dp[i]) {
                    //dp的长度加1
                    dp[i] = dp[j]+1;
                }
            }
            //更新此次循环的最大值
            max = Math.max(max,dp[i]);
        }
        return max;
    }
}

结果如下：

时间复杂度为O(n^2)，空间复杂度为O(n)。

如果追求O(n log n)的话，可以尝试使用二分查找。

文章目录

300最长上升子序列（LeetCode）