Longest increasing subsequence

Given an array, the longest increasing subsequence (LIS) is the longest set of elements, kept in their original order but not necessarily adjacent, where each is strictly larger than the previous. For [10, 9, 2, 5, 3, 7, 101, 18] one LIS is [2, 3, 7, 18], length 4.

The simple DP defines dp[i] = length of the longest increasing subsequence that ends exactly at index i. dp[i] = 1 + max(dp[j]) over j < i with nums[j] < nums[i], and the answer is the maximum dp[i]. That is O(n^2).

The faster method (patience sorting) keeps an array tails where tails[k] is the smallest possible last value of an increasing subsequence of length k + 1. tails is always sorted, so each new number finds its place with binary search in O(log n), giving O(n log n) overall.

1. 1O(n^2): set dp[i] = 1 for all i. For each i, look at every j < i; if nums[j] < nums[i], dp[i] = max(dp[i], dp[j] + 1). Return max(dp).
2. 2O(n log n): start with an empty tails array. For each x, find k = bisect_left(tails, x), the first position with tails[k] >= x.
3. 3If k equals len(tails), x is larger than every tail, so it extends the longest subsequence: append it.
4. 4Otherwise replace tails[k] with x. A subsequence of length k + 1 can now end in a smaller value, which leaves more room for future numbers.
5. 5The answer is len(tails). To recover an actual subsequence, also store, for each element, the index of the element before it at the time it was placed, and walk back from the last tail.
6. 6For non-decreasing (equal values allowed) use bisect_right instead of bisect_left.

from bisect import bisect_left


def lis_quadratic(nums):
    """dp[i] = length of the LIS ending exactly at i. O(n^2)."""
    if not nums:
        return 0
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)


def lis(nums):
    """Patience sorting. O(n log n)."""
    tails = []        # tails[k] = smallest tail of an increasing run of length k+1
    for x in nums:
        k = bisect_left(tails, x)      # first tail >= x
        if k == len(tails):
            tails.append(x)            # extends the longest run
        else:
            tails[k] = x               # better (smaller) tail for length k+1
    return len(tails)

# lis([10, 9, 2, 5, 3, 7, 101, 18]) -> 4

lis_quadratic is the direct DP and also supports variants like counting. lis keeps the smallest tail per length; because tails is sorted, bisect_left finds the spot in O(log n), so the whole run is O(n log n) time and O(n) space.

Cost: O(n^2) time and O(n) space for the simple DP; O(n log n) time and O(n) space with patience sorting.