Intuition

The O(n²) DP tries every previous element. The faster idea: keep an array tails where tails[k] is the smallest tail value of any increasing subsequence of length k+1.

A smaller tail is always at least as useful (it leaves more room to extend), so binary-searching each number into tails keeps it sorted, and its length is the LIS length. This is patience sorting.

Approach

For each number, binary-search the first tail ≥ it.
If none is ≥ it, it extends the longest run → append.
Otherwise replace that tail with this (smaller) value.
The length of tails is the answer.

Walkthrough

nums = [10, 9, 2, 5, 3, 7]
10 -> [10]
9  -> [9]
2  -> [2]
5  -> [2,5]
3  -> [2,3]
7  -> [2,3,7]  -> length 3

Solution

import bisect
def lengthOfLIS(nums):
    tails = []
    for x in nums:
        i = bisect.bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)

Complexity

Time — O(n log n): one binary search per element.
Space — O(n): the tails array.

Common Pitfalls

tails is not itself a valid subsequence — only its length is meaningful.
Use bisect_left for strictly increasing; bisect_right would allow duplicates.

Longest Increasing Subsequence

Example 1

Example 2

Constraints