给你一个整数数组 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
解题思路
惯例办法是应用动静布局，工夫复杂度 O(n^2)。
class Solution { public int lengthOfLIS(int[] nums) { // 定义 dp 数组 // dp[i] 示意以 nums[i] 这个数结尾的最长递增子序列长度 int[] dp = new int[nums.length]; // 初始值填充 1（子序列至多蕴含以后元素本人） Arrays.fill(dp, 1); for (int i = 0; i < nums.length; i++) { for (int j = 0; j < i; j++) { // 假如 dp[0...i-1] 都已知，需要求出 dp[i] // 只须要遍历 nums[0...i-1]，找到结尾比 nums[i] 小的子序列 dp[j] // 而后把 nums[i] 接到最初，就能够造成一个新的递增子序列，长度为 dp[j] + 1 // 显然，可能造成很多种新的子序列，只须要抉择最长的，作为 dp[i] 的值即可 if (nums[i] > nums[j]) { dp[i] = Math.max(dp[i], dp[j] + 1); } } } // 遍历 dp 数组，找出最大值 int res = 0; for (int i = 0; i < dp.length; i++) { res = Math.max(res, dp[i]); } return res; }}这边采纳 Vue 中 DOM diff 的思路，即贪婪法，须要留神的是，最初 stack 的长度是对的，然而内容可能不是正确的。因为采纳了两层循环遍历，工夫复杂度为 O(n^2) 。
var lengthOfLIS = function (nums) { let stack = []; for (let i = 0; i < nums.length; i++) { // 数组为空间接入栈，不为空则获取栈顶元素判断大小 if (stack.length == 0 || getTopEle(stack) < nums[i]) { stack.push(nums[i]); } else { let index = findNextEle(stack, nums[i]); stack[index] = nums[i]; } } return stack.length;};function getTopEle(arr) { if (!arr.length) return 0; return arr[arr.length - 1];}function findNextEle(arr, n) { // 判断大小用 >= ，即不替换栈顶元素 return arr.findIndex(item => item >= n);}进一步优化，能够将 findIndex 办法替换为二分查找，工夫复杂度升高到 O(nlogn) 。
参考
精读《DOM diff 最长回升子序列》