Recursion & DP Target: 15s
Patience sorting: maintain smallest possible tails. bisect_left finds where to place each element.
import bisect
def lengthOfLIS(nums):
tails = [] # tails[i] = smallest tail of IS of length i+1
for x in nums:
pos = bisect.bisect_left(tails, x)
if pos == len(tails):
tails.append(x)
else:
tails[pos] = x
return len(tails)Type it from memory. Go.