☆☆☆☆思路：本题是经典的LIS问题。两种解法，动态规划 和 二分查找。
方法1：动态规划。时间复杂度为O(n^2)
方法2：二分查找，时间复杂度为O(nlogn)
【举一反三】： （1）该题为不连续的情况，延伸求最长连续递增子序列长度，见LeetCode674. 最长连续递增序列
（2）除了要会求子序列的长度，还要会求出最长的子序列是什么。
代码1：动态规划
class Solution { /** * dp[i]表示 以nums[i]为结尾的最长上升子序列的长度 * 初始化：都为 1.每个数都单独是长度为1的上升子序列 */ public int lengthOfLIS(int[] nums) { if (nums == null || nums.length == 0) return 0; int[] dp = new int[nums.length]; Arrays.fill(dp, 1); int res = 1; // dp[0]为1， 从 nums[1]开始递推 for (int i = 1; i < nums.length; i++) { for (int j = 0; j < i; j++) { // nums[i] 可以跟在 nums[j] 后面 if (nums[j] < nums[i]) { // 以哪个数结尾的最大递增子序列更大，就选其作为倒数第二个数 dp[i] = Math.max(dp[i], dp[j] + 1); } } res = Math.max(res, dp[i]); // 所有dp[i]中取最大的 } return res; } }
补充：如何根据dp数组求出最长递增子序列是什么？------------参考左神P203
private int[] generateLIS(int[] nums) { int[] dp = new int[nums.length]; Arrays.fill(dp, 1); for (int i = 1; i < nums.length; i++) { for (int j = 0; j < i; j++) { if (nums[j] < nums[i]) { dp[i] = Math.max(dp[i], dp[j] + 1); } } } // Step1. 遍历dp数组，找到最大值以及位置; int len = 0; // 最大值，也即最长递增子序列的长度 int index = 0; for (int i = 0; i < dp.length; i++) { if (dp[i] > len) { len = dp[i]; index = i; } } int[] lis = new int[len]; lis[--len] = nums[index]; // 最长递增子序列以nums[index]结尾 // Step2. 每次从右向左遍历，寻找当前数的前一个数(满足1.比当前数的值小;2.比当前数对应的dp值小1) for (int i = index - 1; i >= 0; i--) { if (nums[i] < nums[index] && dp[i] == dp[index] - 1) { lis[--len] = nums[i]; index = i; } } return lis; }
代码2：二分查找
M