Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence keeps the original order but may skip elements.
[2,3,7,101].- 1 <= nums.length <= 2500
- -10^4 <= nums[i] <= 10^4
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Trying every subsequence is O(2^n). DP state: dp[i] = length of the longest increasing subsequence that ends exactly at i. Recurrence: dp[i] = 1 + max(dp[j]) over j < i with nums[j] < nums[i], or 1 if none. Base: every dp[i] starts at 1. The answer is max(dp), giving O(n^2). The faster idea keeps a tails array: tails[k] is the smallest tail of any increasing run of length k + 1. tails is always sorted, so for each x we binary search the first value >= x and replace it with x (a smaller tail is never worse), or append x if it is bigger than all. The length of tails is the answer.
Algorithm
- Start with an empty list
tails. - For each
xinnums, findi, the first index withtails[i] >= x(lower bound). - If
iequals the length oftails, appendx; otherwise settails[i] = x. - Return the length of
tails.
O(n log n)Space: O(n)tails is not an actual increasing subsequence, only its length is meaningful. If the interviewer asks you to print the sequence, store a parent index for every element (easy with the O(n^2) DP) and walk back from the end.class Solution: def lengthOfLIS(self, nums: List[int]) -> int: tails = [] # tails[k] = smallest tail of an increasing run of length k + 1 for x in nums: i = bisect_left(tails, x) # first tail >= x if i == len(tails): tails.append(x) else: tails[i] = x return len(tails)