300. Longest Increasing Subsequence

public int lengthOfLIS(int[] nums) { if (nums == null || nums.length == 0) return 0; // dp[i] 以i坐标结尾的 列表 的 LIS长度 int[] dp = new int[nums.length]; dp[0] = 1; if (nums.length == 1) return 1; int maxAns = 0; for (int i = 1; i < dp.length; i++) { int maxVal = 0; for (int j = 0; j < i; j++) { if (nums[i] > nums[j]) // maxVal dp[j]的最大值 maxVal = Math.max(maxVal, dp[j]); } // 如果maxVal == 0 说明 nums[i] <= nums[j]，否则 nums[i] > nums[j]所以肯定 + 1 dp[i] = maxVal + 1; maxAns = Math.max(maxAns, dp[i]); } return maxAns; } public int lengthOfLIS(int[] nums) { int n = nums.length; int[] tails = new int[n]; int len = 0; for (int x : nums) { int lo = 0, hi = len; // 找到第一个 >= x 的下标 while (lo < hi) { int mid = lo + (hi - lo) / 2; if (x > tails[mid]) lo = mid + 1; else hi = mid; } tails[lo] = x; if (lo == len) len++; } return len; }