动态规划解决最长递增子序列问题

一、问题介绍

首先我来介绍一下什么是最长递增子序列问题，要知道什么是最长递增子序列问题，我们必须先明白一个概念，那就是什么是子序列，所谓子序列，就是将给定序列中零个或多个元素去掉之后得到的序列。那么递增的子序列就是指该序列中的元素数值是随着下标增大逐渐增大的。而其中最长的递增子序列的长度和该子序列就是我们这个问题需要求解的值。

二、算法

所谓动态规划就是首先将大问题拆分为小问题，而其最关键的是避免了这些小问题的重复解决，而是保留这个小问题的解下一次直接使用。在使用动态规划时，最关键的就是其中的递推公式。最长递增子序列的递推公式为 $F[i]=max(1,F[j]+1) , a_{j}<a_{i} && j<i$，$F[0]=1$，其中$F[0]=1$。假设有序列$\lbrace a_{1}, a_{2},…a_{n} \rbrace$，我们用 $F[i]$代表若递增子序列以$a_{i}$结束时它的最长长度，对于$F[0]$我们易知其值为1。那么对于任意一个$F[i]$，我们只需要在下标小于它的元素中找到数值小于它的最大的F值,那么最大的$F[i]$就相当于找到的F值加上1。之后遍历整个序列一遍就能够得到整个序列中每一个元素的以其结尾的最长递增子序列长度，那么我们自然也就得到了整个序列的最长递增子序列长度。同时我通过得到的动态规划表回溯得到其中的一个最长递增子序列。

三、代码实现

在代码实现中，我使用了python来实现这一个算法，使用一个字典来记录动态规划表，之后从头遍历序列中的每一个元素，对于每一个元素又要遍历其之前的元素值。最后遍历完成后返回字典中的值的最大值就找到了该序列的最长递增子序列的长度。之后我从字典其中的一个最大值的key开始回溯得到其中的一个最长递增子序列，其中回溯的条件是前面的值小于后面的值且记录F值的longest字典对应的值相差1。

代码：

def solveLIS(A):
    result=[]
    longest={}
    longest[0]=1
    for i in range(1,len(A)):
        maxlen=-1
        for j in range(0,i):
            if A[i]>A[j] and maxlen<longest[j]:
                maxlen = longest[j]
            if maxlen >= 1:
                longest[i]=maxlen+1
            else:
                longest[i]=1 
                
    maxlen = max(longest.values())
    maxkey = 0
    for i in range(len(A)-1,-1,-1):
        if longest[i] == maxlen:
            maxkey = i
            break
    result.append(A[maxkey])
    maxlen=maxlen-1
    for i in range(maxkey-1,-1,-1):
        if result[-1] > A[i] and longest[i] == maxlen:
            maxlen=maxlen-1
            result.append(A[i])
        if maxlen<=0:
            break
    result = result[::-1]
    return max(longest.values()),result

A=[5,2,8,6,3,6,9,7]
print(solveLIS(A))
B=[3,2,5,6,7,1,8,9]
print(solveLIS(B))

结果：

(4, [2, 3, 6, 7])
(6, [2, 5, 6, 7, 8, 9])