【LeetCode】最长递增子序列 [M]（动态规划）_最长递增子序列leetcode

300. 最长递增子序列 - 力扣（LeetCode）

一、题目

给你一个整数数组 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 。

示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：

• 1 <= nums.length <= 2500
• -104 <= nums[i] <= 104

二、代码

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
 
        //int[] dp = new int[nums.length];
        int[] end = new int[nums.length];
        //dp[0] = 1;
        end[0] = nums[0];
        // 记录当前end数组最右边有数的位置
        int endIndex = 0;
        // 初始值是1，数组中只有1个数的话，最大的递增子序列长度就是1
        int maxLen = 1;
 
        for (int i = 1; i < nums.length; i++) {
            // 划定end数组的有效范围，开始二分查找
            int l = 0;
            int r = endIndex;
            // 二分查找
            while (l <= r) {
                int mid = (l + r) >> 1;
                // 如果此时nums[i]比end[mid]大，说明我们要在找到的长度最大的比nums[i]大的end数组上的数一定在右半部分
                if (end[mid] < nums[i]) {
                    l = mid + 1;
                // 否则去左半部分
                } else {
                     r = mid - 1;
                }
 
                // if (end[mid] > nums[i]) {
                //     r = mid - 1;
                // } else {
                //     l = mid + 1;
                // }
            }
 
            // l > endIndex 说明end扩充了
            if (l > endIndex) {
                //dp[i] = endIndex + 1;
                end[++endIndex] = nums[i];
            // end没有被扩充，修改原有的end数组对应的值
            } else {
                if (end[l] > nums[i]) {
                    end[l] = nums[i];
                    //dp[i] = l + 1 + 1;
                }
            }
 
            // 找到做大的长度
            maxLen = Math.max(maxLen, l + 1);
        }
 
        return maxLen;
    }
}

三、解题思路 

一般子序列的这种题我们就使用动态规划求解。以i位置结尾的子序列怎么怎么样，以这个角度去写动态规划。只要把所有位置作为某一个子序列的结尾的最大值都求出来，然后在里面取最大值，肯定就能把最终答案求出来，不会有遗漏子序列的情况。

这个优化点就是引入了end数组，这个数字将我们需要的信息有序化，进而可以使用二分法实现快速查找，就不用在dp数组中进行遍历茶中了，因为dp数组中的数据并不是有序的，毕竟不能用二分。