最長(zhǎng)遞增子序列: 動(dòng)態(tài)規(guī)劃和LCS(最長(zhǎng)公共子序列)
子序列和子串的區(qū)別：子序列不連續(xù)，字串連續(xù)。
這個(gè)題兩種解法

1. 動(dòng)態(tài)規(guī)劃
2. 復(fù)制數(shù)組并排序，求兩數(shù)組的最長(zhǎng)公共子序列。

下面分別做簡(jiǎn)單介紹：

動(dòng)態(tài)規(guī)劃

O(n^2)時(shí)間復(fù)雜度。想求的array[0, i]的最大遞增子序列。則計(jì)算array[0, i- 1]中以各元素為最后元素的最長(zhǎng)遞增序列。與array[i]比較, 因?yàn)椴贿B續(xù)。

def longest_increasing_subsequence_one(array):
    temp_array = [1] * len(array)
    for index, _ in enumerate(array):
        for i in range(0, index):
            if array[i] < array[index] and temp_array[i] + 1 >= temp_array[index]:
                temp_array[index] = temp_array[i] + 1
    return max(temp_array)

LCS ：最長(zhǎng)公共子序列

也是動(dòng)態(tài)規(guī)劃。
若兩序列A[i]的元素和B[i]的元素相等，那么最長(zhǎng)公共子序列為A[0, i -1], B[0, j - 1]的最長(zhǎng)公共子序列的值加1。否則分別是A[0, i- 1], B[0 ,j] 或者A [0, i - 1], B[0, j ]的最長(zhǎng)公共子序列的較大值。
其中選擇一個(gè)二維數(shù)組來(lái)標(biāo)記記住A[i], B[j]的最長(zhǎng)公共子序列，見代碼。

#復(fù)制列表并排序，求兩列表的最長(zhǎng)公共子序列( LCS ): 動(dòng)態(tài)規(guī)劃
def longest_increasing_subsequence_two(array):
    copy_array = array[:]
    copy_array.sort()
    #中間結(jié)果
    temp_array = [[0 for i in range(len(array))] for j in range(len(copy_array))]
    for i in range(1, len(array)):
        for j in range(1, len(copy_array)):
            if array[i] == copy_array[j]:
                temp_array[i][j] = temp_array[i - 1][j - 1] + 1
            else:
                temp_array[i][j] = max(temp_array[i][j - 1],  temp_array[i - 1][j])
    #倒推求出最長(zhǎng)公共子序列
    result = []
    i = len(array) - 1
    j = len(copy_array) - 1
    while i > 0 and j > 0:
        if array[i] == copy_array[j]:
            result.append(array[i])
            i -= 1
            j -= 1
        else:
            if temp_array[i][j - 1] >= temp_array[i - 1][j]:
                j -= 1
            else:
                i -= 1
    result.reverse()
    print(result)
    print(len(result))