LongestIncreasingSubsequence.md

Longest Increasing Subsequence

背景知识

升序/降序子字符串: 一个字符串的子字符串是指一个字符串中的字符按在字符串中的顺序组成的字符集。如5,3,4 是字符串5,1,3,4,2的子字符串，如果这个字符串是升序或降序，即字符串的升序/降序子字符串。

问题

给定：给定一个字符串

输出：这个字符串的最长升序和降序子字符串

解决

求字符串的最长升序/降序子字符串是一个典型的leecode算法题，大体思路是遍历字符串，如果符合升序/降序，存入子字符串集合。 判断符合升序/降序的方法是通过二分查找，如果返回的元素下标是第一个，则不符合升序/降序。存入子字符串集合，同时用字典记录 这个元素的上一个元素，如果不符合，则覆盖子字符串的第一个元素，同时，字典中记录这个元素的上一个元素为空。在遍历结束后， 取子字符串集合的最后一个字符，按字典求上一个字符，拼接完成最长子字符串。

def bisect_ascending(a, x, lo=0, hi=None):
    '''
    二分查找找到元素在已有递增序列中的位置
    '''
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x: lo = mid+1
        else: hi = mid
    return lo

def bisect_descending(a, x, lo=0, hi=None):
    '''
    二分查找找到元素在已有递减序列中的位置
    '''
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] > x: lo = mid+1
        else: hi = mid
    return lo

def longest_increasing_subsequence(seq, n):
    tops = []
    links = {}

    for elem in seq:
        i = bisect_ascending(tops, elem)
        if i == len(tops):
            tops.append(elem)
        else:
            tops[i] = elem
        links[elem] = tops[i - 1] if i > 0 else None

    lisubseq = [tops[-1]]
    while links[lisubseq[-1]]:
        lisubseq.append(links[lisubseq[-1]])

    lisubseq.reverse()
    return lisubseq

def longest_decreasing_subsequence(seq):
    tops = []
    links = {}

    for elem in seq:
        i = bisect_descending(tops, elem)
        if i == len(tops):
            tops.append(elem)
        else:
            tops[i] = elem
        links[elem] = tops[i - 1] if i > 0 else None
        print(elem, i, tops, links)

    ldsubseq = [tops[-1]]
    while links[ldsubseq[-1]]:
        ldsubseq.append(links[ldsubseq[-1]])

    ldsubseq.reverse()
    return ldsubseq

print(timeit.timeit("longest_decreasing_subsequence(%s)" % str(a), setup="from __main__ import longest_decreasing_subsequence")) # 7.4754391469999995

这个方法执行效率很高的，可以达到O(nlogn),一个问题是不能处理重复的字符，因为字典的key是唯一的。

我也写了一种效率更低的方法，比较暴力的遍历找到所有升序/降序字符串，再判断长度。这种方法执行效率为O(n^2), 从执行时间上也能看出，对 示例中的数列运算时间差也能达到30倍。

def lis_3(x,reverse_item=True):
    '''
    可以适应重复元素，效率相应降低
    '''
    N = len(x)
    subseq = []
    for i in range(N):
        if i == 0:
            subseq.append([x[i]])
        else:
            for subi in range(len(subseq)):
                if reverse_item:
                    choose = x[i]<=subseq[subi][-1]
                else:
                    choose = x[i]>=subseq[subi][-1]
                if choose:
                    newarr = copy.deepcopy(subseq[subi])
                    newarr.append(x[i])
                    subseq.append(newarr)
            subseq.append([x[i]])

    longth = 0
    ans = None
    for i in subseq:
        if len(i)>longth:
            longth = len(i)
            ans = i
    return ans

a = [5,6,4,2,9,4,3,1]
print(lis_3(a)) # [5, 4, 4, 3, 1]
print(timeit.timeit("lis_3(%s)" % str(a), setup="from __main__ import lis_3")) # 231.170936291

扩展

当比较两个染色体的基因时，一个简单的方法就是将基因在一个染色体中出现的顺序标记，找出这些基因在另一个染色体上的相同顺序的子串。