Longest Increasing Subsequence

Write `length_of_lis(nums)` returning the length of the longest strictly increasing subsequence. Elements need not be contiguous. length_of_lis([10,9,2,5,3,7,101,18]) -> 4 (2,3,7,101) The O(n^2) DP is a fine first answer. The O(n log n) version keeps an array where position i holds the smallest possible tail of an increasing subsequence of length i+1, and binary searches for where each value belongs. That array is not itself a valid subsequence — only its length is meaningful.