longest_increasing_subsequence.py

import bisect
from typing import List


class Solution:
    """LeetCode #300 - Longest Increasing Subsequence (Medium)
    https://leetcode.com/problems/longest-increasing-subsequence/

    Length of the longest strictly increasing subsequence. Elements keep their
    order but need not be adjacent.
    """

    def lengthOfLIS(self, nums: List[int]) -> int:
        """O(n log n) via patience sorting.

        `tails[i]` holds the smallest value that can end an increasing
        subsequence of length i + 1. That array is sorted, so binary search
        finds where each number belongs.

        A number either extends the longest run (append) or replaces the first
        tail >= itself. Replacing looks destructive but is not: a smaller tail at
        the same length can only make future numbers easier to place, and the
        length never drops.

        `tails` is not itself a valid subsequence - only its length is the
        answer. Reconstructing the actual sequence needs a parent array.

        Time:  O(n log n)
        Space: O(n)
        """
        tails: List[int] = []

        for num in nums:
            # bisect_left, not bisect_right: strictly increasing means an equal
            # value must replace rather than extend.
            i = bisect.bisect_left(tails, num)
            if i == len(tails):
                tails.append(num)
            else:
                tails[i] = num

        return len(tails)

    def lengthOfLIS_quadratic(self, nums: List[int]) -> int:
        """The O(n^2) version, which is the one to derive first.

            best[i] = 1 + max(best[j]) over j < i with nums[j] < nums[i]

        Time:  O(n^2)
        Space: O(n)
        """
        if not nums:
            return 0

        best = [1] * len(nums)
        for i in range(1, len(nums)):
            for j in range(i):
                if nums[j] < nums[i]:
                    best[i] = max(best[i], best[j] + 1)

        return max(best)