[ROSALIND] Longest Increasing Subsequence

相當經典的題目。


一般的 dynamic programming 的時間複雜度是 O(n^2)

def LIS(sequence):
    # Time complexity is O(n^2)    
    lis_len = [1] * len(sequence)
    for i in range(len(sequence)):
        for j in range(i+1, len(sequence)):
            if sequence[i] < sequence[j]:
                lis_len[j] = max(lis_len[j], lis_len[i] + 1)
    rv = []
    curr_len = max(lis_len)
    for i in range(len(sequence) - 1, -1, -1):
        if curr_len == lis_len[i]:
            rv.append(sequence[i])
            curr_len -= 1
    return rv[::-1]

如果我們使用 Robinson-Schensted-Knuth Algorithm 改良的版本：

def LIS(sequence):
    # Robinson-Schensted-Knuth Algorithm
    # Time complexity is O(n log(n))
    if not sequence:
        return []
    aux_len = [1]
    aux_rv = [sequence[0]] 
    for i in range(1, len(sequence)):
        x = sequence[i]
        if x > aux_rv[-1]:
            aux_rv.append(x)
            aux_len.append(len(aux_rv))
        else:
            j = bisect.bisect_right(aux_rv, x)
            aux_rv[j] = x
            aux_len.append(j + 1)        
    rv = []
    curr_len = len(aux_rv)
    for i in range(len(sequence) - 1, -1, -1):
        if curr_len == aux_len[i]:
            rv.append(sequence[i])
            curr_len -= 1
    return rv[::-1]

這個時間複雜度是 O(n log(n))，關鍵就是用 binary search 把時間複雜度從 n 降成 log(n)。