【Leetcode 热题 100】300. 最长递增子序列

问题背景

给你一个整数数组 $nums$，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，$[3,6,2,7]$ 是数组 $[0,3,1,6,2,2,7]$ 的子序列。

数据约束

• $1\le nums.length\le 2500$
• $-10^4\le nums[i]\le 10^4$

解题过程

子序列而不是子数组，优先考虑回溯法而不是滑窗。
递归方法中必须要有一个下标表示当前要选择的数字的位置，选或不选的方法还需要额外记录子序列中前一个数相关的信息，否则不能保证严格递增。因此，这题选择选哪一个的做法代码更简洁。

对于动态规划问题，有一种优化时间复杂度的方案是交换状态和状态值，这题可以在数组中维护子序列末尾元素的最小值，遍历数组的过程中只有两种操作：添加或修改元素。
修改的一定是不小于当前元素的第一个元素，如果没有这样的元素，就应将新元素添加到末尾。
配合二分查找，这样可以将时间效率优化到 $O(NlogN)$ 这个量级。

具体实现

递归

class Solution {private int[] nums;private int[] memo;public int lengthOfLIS(int[] nums) {this.nums = nums;int n = nums.length;memo = new int[n];int res = 0;for (int i = 0; i < n; i++) {res = Math.max(res, dfs(i));}return res;}private int dfs(int i) {if(memo[i] > 0) {return memo[i];}for (int j = 0; j < i; j++) {if(nums[j] < nums[i]) {memo[i] = Math.max(memo[i], dfs(j));}}return ++memo[i];}
}

递推

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

贪心

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