124、★最长递增子序列-LeetCode-300

题目：

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

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

 
示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-increasing-subsequence

思路：

1. 状态的说明：①到nums[i]处，最长子序列；②以nums[i]结尾，最长子序列

代码1是以nums[i]结尾；这个还是最容易理解和实现的！

2.二分法：最长子序列的结尾元素实时更新，因为结尾元素越小，后面连接上的概率就越大！

二分法的写法有很多种；

重要的是将所有的情况都比较到，并且有合适的结束条件！

还要注意最后定位的位置；

判断条件也很重要

代码：

1. 动态规划：将状态表示为：以nums[i]结尾的最长子序列！

时间复杂度为O(N^2)，以nums[i]为结尾，需要遍历之前所有的dp

class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
 
        //dp数组的含义是，到当前下标，此前的最长递增子序列长度
        int len = nums.length;
        int[] dp = new int[len];
        Arrays.fill(dp,1);
        int res = 1;//到这里最短为1
        for(int i = 1;i < len;i++){
            for(int j = 0;j < i;j++){
                if(nums[i] > nums[j]){
                    dp[i] = Math.max(dp[i],dp[j] + 1);
                }
            }
            res = Math.max(res,dp[i]);
        }
        return res;
    }
}

2. 二分法进行时间复杂度的优化，O(N*logN)

class Solution {
    public int lengthOfLIS(int[] nums) {
            if(nums == null || nums.length == 0) return 0;
            int len = nums.length;
 
            int[] temp = new int[len + 1];
            int maxLen = 1;
            temp[maxLen] = nums[0];
            for(int k = 1;k < nums.length;k++){
                if(nums[k] > temp[maxLen]){
                    temp[++maxLen] = nums[k];
                }
                //可能是小于或等于
                else{
                    //二分法更新数组temp;二分法写法有很多种，主要包括所有情况即可
                    int i = 1,j = maxLen;
                    while(i < j){
                        int mid = (i + j) / 2;
                        if(temp[mid] < nums[k]){
                            i = mid + 1;
                        }else{
                            j = mid;
                        }
                    }
                    temp[i] = nums[k];
                }
            }
            return maxLen;
        }
}