一、题目

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

点击查看原题

二、思路

1、动态规划

本题属于较为经典的动态规划，设立数组dp，dp[i]为以nums[i]结尾的递增子序列最长值。状态转移方程如下：

dp[i]的初始值为1.

2、贪心+二分

想让递增子序列最长，则需要让该序列尽可能增长最慢。
使用一个无序递增数组（无序指不按照nums中的序列，多个递增序列都放在一个数组中，这点下面会解释）来记录最长递增子序列。设定一个数组memo：

1）如果nums[i]>memo[memo.size()-1]，则在memo末尾添加nums[i]，代表递增子序列长度+1 2）如果nums[i]<=memo[memo.size()-1]，说明nums[i]不能直接添加进目前的最长递增子序列中，二分查找以它为末尾的最长子序列长度，并覆盖memo中大于等于nums[i]的元素，如果后续会使用nums[i]所在序列，memo中的元素会慢慢被替代，直到长度超过当前的memo.size()。（这部分自己多写几次代码，手推代码去理解）

三、代码

1、动态规划

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int ans = 1;
        for (int i = 0; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = i-1; j >= 0; j--) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}

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

2、贪心+二分

class Solution {
    public int lengthOfLIS(int[] nums) {
        List<Integer> memo = new ArrayList();
        memo.add(nums[0]);
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > memo.get(memo.size()-1)) {
                memo.add(nums[i]);
            } else {
                int loc = find(memo, nums[i]);
                memo.set(loc, nums[i]);
            }
        }
        return memo.size();
    }
    public int find(List<Integer> memo, int num) {
        int start = 0, end = memo.size();
        while (start < end) {
            int mid = (start + end) / 2;
            if (memo.get(mid) == num) {
                return mid;
            } else if (memo.get(mid) > num) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }
}

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