longest increasing subsequence

After finishing my solution for Day 02, I went reading through other people’s solutions to learn more.

There, I ran into the longest increasing subsequence problem. This seems like something that could come in handy later so it’s learning time!

Longest increasing subsequence algorithm finds a subset of numbers from the original sequence in a way that the numbers are always increasing, they are not switched around from their original order and the result is the longest possible outcome.

Wikipedia has this example:

In the first 16 terms of the binary Van der Corput sequence

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15

one of the longest increasing subsequences is

0, 2, 6, 9, 11, 15

This subsequence has length six; the input sequence has no seven-member increasing subsequences. The longest increasing subsequence in this example is not the only solution: for instance,

0, 4, 6, 9, 11, 15

0, 2, 6, 9, 13, 15

0, 4, 6, 9, 13, 15

are other increasing subsequences of equal length in the same input sequence.

Following the algorithm in Wikipedia article, I put together this Python function:

def longest_increasing_subsequence(seq):
    """
    algorithm from https://en.wikipedia.org/wiki/Longest_increasing_subsequence
    """
 
    # Initialize two lists, one length of original sequence
    # and another that is one longer and starts with -1
    sequence_length = len(seq)
    predecessor_indices = [None] * sequence_length
    smallest_value_indices = [None] * (sequence_length + 1)
    smallest_value_indices[0] = -1
 
    # Keep track of the known longest subsequence
    longest_subseq_length = 0
 
    # Loop over the sequence
    for idx, value in enumerate(seq):
        # Do a binary search for the smallest positive l ≤ longest_subseq_length
        lo = 1
        hi = longest_subseq_length + 1
 
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if seq[smallest_value_indices[mid]] >= value:
                hi = mid
            else:
                lo = mid + 1
 
        new_longest_subseq_length = lo
        predecessor_indices[idx] = smallest_value_indices[new_longest_subseq_length - 1]
        smallest_value_indices[new_longest_subseq_length] = idx
 
        # If we found a new longest subsequence length, update the variable
        if new_longest_subseq_length > longest_subseq_length:
            longest_subseq_length = new_longest_subseq_length
 
    result = [None] * longest_subseq_length
    k = smallest_value_indices[longest_subseq_length]
    for j in range(longest_subseq_length - 1, -1, -1):
        result[j] = seq[k]
        k = predecessor_indices[k]
 
    return result