定个小目标之刷LeetCode热题（28）
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 。
今天是刷这道题，看题目名称就能猜到要用到动态规划思想，本题使用动态规划+二分查找进行求解，定义一个dp[i]数组，其含义表示以nums[i]结尾的递增子序列的长度为i,那么我们遍历数组，每遇到nums[i] < nums[j]时就将其放入dp数组，即dp[++i] = nums[j],如果遇到nums[i] >= nums[j],那么我们需要把dp数组中比nums[j]大的第一个数替换掉，例如下面的nums[]和dp[]，会发现2,3,7,8都是递增的，都可以放入到dp[]，当遍历到6时，我们需要在dp中寻找第一个比6大的数字，然后把其替换掉，如例子中第一个比6大的数是7，那么我们把7替换为6，在遍历数组过程中我们需要维护一个len用来记录dp[]的最大长度。
nums[]: 2,3,7,8,6,9
dp[]: 2,3,6,8,9
直接上代码如下，代码是使用二分查找在dp数组中找最后一个小于nums[i]的数字,并记录其索引pos，然后 dp[pos + 1] = nums[i]
class Solution {public int lengthOfLIS(int[] nums) {int length = nums.length;if (length == 1)return 1;int[] dp = new int[length + 1];int len = 1;dp[len] = nums[0];for (int i = 1; i < length; i++) {if (dp[len] < nums[i]) {dp[++len] = nums[i];} else {// 在dp数组中二分查找最后一个小于nums[i]的数字,pos记录其下标int l = 1, r = len, pos = 0;while (l <= r) {int mid = (l + r) / 2;if (dp[mid] < nums[i]) {pos = mid;l = mid + 1;} else {r = mid - 1;}}// 把nums[i]放到dp数组中最后一个小于nums[i]元素的后一位dp[pos + 1] = nums[i];}}return len;}
}题目链接：题单 - 力扣（LeetCode）全球极客挚爱的技术成长平台