Description
Return the length of a strictly increasing subsequence; selected entries need not be adjacent.
Solution
from bisect import bisect_left
def length_of_lis(nums):
tails = []
for value in nums:
i = bisect_left(tails,value)
if i == len(tails):
tails.append(value)
else:
tails[i] = value
return len(tails)Examples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[3,1,2,5]]- Output
3
1, 2, 5 is strictly increasing.
Example 2
- Input
[[2,2,2]]- Output
1
Equal values cannot extend a strict subsequence.
Example 3
- Input
[[5,4,3]]- Output
1
Every increasing subsequence has one value.
Approach
Maintain the smallest possible tail for every length. Binary search the first tail greater than or equal to each value.
Time & space
O(n log n) time; O(n) space. Here n is the input length.