The problem
A subsequence keeps some elements of an array in their original order, not necessarily next to each other. Given nums, return the length of the longest subsequence whose values strictly increase.
Examples
- Input
nums = [10, 9, 2, 5, 3, 7, 101, 18]
- Output
4
- Input
nums = [0, 1, 0, 3, 2, 3]
- Output
4
- Input
nums = [7, 7, 7, 7, 7, 7, 7]
- Output
1
Constraints
- 1 ≤ nums.length ≤ 2500
- −10⁴ ≤ nums[i] ≤ 10⁴
The idea
The O(n²) way asks, for each element, what is the longest increasing run ending there. A sharper question: for each length k, what is the smallest value an increasing run of that length can end with? Call it tails[k]. A smaller ending is always better — it leaves more room to extend.
tails only ever increases along its length, so each new number x finds its place by binary search: the first tail ≥ x. If there is none, x extends the longest run and tails grows; otherwise x replaces that tail — a run of that length can now end lower. The length of tails is the answer (tails itself need not be a real subsequence).
- Time
- O(n log n)
- Space
- O(n)
Solution · every language run against every case
class Solution: def lengthOfLIS(self, nums: List[int]) -> int: # tails[k]: the smallest last value of any increasing run of length k + 1 seen so far. # tails is itself increasing, so each number finds its place by binary search. tails = [] for x in nums: k = bisect_left(tails, x) # the first tail >= x if k == len(tails): tails.append(x) # x extends the longest run else: tails[k] = x # a run of length k + 1 can now end lower return len(tails)