# 300. Longest Increasing Subsequence     ## Approach 1: 2D DP

• Time: $O(n^2)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public: int lengthOfLIS(vector& nums) { if (nums.empty()) return 0; // dp[i] := Length of LIS ending at nums[i] vector dp(nums.size(), 1); for (int i = 1; i < nums.size(); ++i) for (int j = 0; j < i; ++j) if (nums[j] < nums[i]) dp[i] = max(dp[i], dp[j] + 1); return *max_element(dp.begin(), dp.end()); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public int lengthOfLIS(int[] nums) { if (nums.length == 0) return 0; // dp[i] := Length of LIS ending at nums[i] 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); return Arrays.stream(dp).max().getAsInt(); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution: def lengthOfLIS(self, nums: List[int]) -> int: if not nums: return 0 # dp[i] := LIS ending at nums[i] dp =  * len(nums) for i in range(1, len(nums)): for j in range(i): if nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1) return max(dp) 
• Time: $O(n\log n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public: int lengthOfLIS(vector& nums) { // tail[i] := the min tail of all increasing subseqs having length i + 1 // It's easy to see that tail must be an increasing array. vector tail; for (const int num : nums) if (tail.empty() || num > tail.back()) tail.push_back(num); else tail[firstGreaterEqual(tail, num)] = num; return tail.size(); } private: // Finds the first index l s.t A[l] >= target. // Returns A.size() if can't find. int firstGreaterEqual(const vector& A, int target) { return lower_bound(A.begin(), A.end(), target) - A.begin(); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution { public int lengthOfLIS(int[] nums) { // tail[i] := the min tail of all increasing subseqs with length i + 1 // It's easy to see that tail must be an increasing array. List tail = new ArrayList<>(); for (final int num : nums) if (tail.isEmpty() || num > tail.get(tail.size() - 1)) tail.add(num); else tail.set(firstGreaterEqual(tail, num), num); return tail.size(); } // Finds the first index l s.t A.get(l) >= target. // Returns nums.size() if can't find. private int firstGreaterEqual(List A, int target) { int l = 0; int r = A.size(); while (l < r) { final int m = (l + r) / 2; if (A.get(m) >= target) r = m; else l = m + 1; } return l; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution: def lengthOfLIS(self, nums: List[int]) -> int: # tail[i] := the min tail of all increasing subseqs having length i + 1 # It's easy to see that tail must be an increasing array. tail = [] for num in nums: if not tail or num > tail[-1]: tail.append(num) else: tail[bisect.bisect_left(tail, num)] = num return len(tail)