最长递增子序列问题

最长递增子序列（Longest Increasing Subsequence，LIS）问题：给定一个序列，求解其中最长的递增子序列的长度的问题。

要求长度为i的序列的Ai{a1,a2,…,ai}最长递增子序列，需要先求出序列Ai-1{a1,a2,…,ai-1}中以各元素(a1,a2,…,ai-1)作为最大元素的最长递增序列，然后把所有这些递增序列与ai比较，如果某个长度为m序列的末尾元素aj(j<i)比ai要小，则将元素ai加入这个递增子序列，得到一个新的长度为m+1的新序列，否则其长度不变，将处理后的所有i个序列的长度进行比较，其中最长的序列就是所求的最长递增子序列。

以[3, 1, 4, 5, 9, 2, 6, 5, 0]为例。前面每有一个小于自己的，序号就加一。

代码：

def getdp1(arr):
    n = len(arr)
    dp = [0] * n  # 排序
    for i in range(n):
        dp[i] = 1
        for j in range(i):
            if arr[i] > arr[j]:  # 前面每有一个小于己的，序列号加1
                dp[i] = max(dp[i], dp[j] + 1)
    return dp


def generateLIS1(arr):
    dp = getdp1(arr)
    n = max(dp)
    index = dp.index(n)  # 获取最大值的序号
    lis = [0] * n
    n -= 1  # 因为列表从0开始，所有n减1
    lis[n] = arr[index]  # 将子序列末尾的序号赋值
    # 从右向左
    for i in range(index, - 1, -1):
        # 关键
        if arr[i] < arr[index] and dp[i] == dp[index] - 1:  # 如果序列的值小于末尾值，且编号为末尾序号减1
            n -= 1
            lis[n] = arr[i]  # 赋值给列表
            index = i  # 序号为该i
    return lis

输出：[1, 4, 5, 9]

可以对代码进行改进。

基于此序列的严格递增性，利用二分查找，找到最大元素刚好小于aj的元素bk，将aj加入这个序列尾部，形成长度为k+1但是最大元素又小于bk+1的新序列，取代之前的bk+1，如果aj比Bn中的所有元素都要大，说明发现了以aj为最大元素，长度为n+1的递增序列，将aj作Bn+1的第n+1个元素。从b1依次递推，就可以在O(nlgn)的时间内找出序列A的最长递增子序列

代码：

def getdp2(arr):
    n = len(arr)
    dp, ends = [0] * n, [0] * n  # dp存放排序，ends是对比用的新列表
    ends[0], dp[0] = arr[0], 1
    right, l, r, m = 0, 0, 0, 0
    for i in range(1, n):  # 因为0已赋值，所以从1开始
        l = 0
        r = right
        # 二分查找，若找不到则ends[l或r]是比arr[i]大而又最接近其的数
        # 若arr[i]比ends有效区的值都大，则l=right+1
        while l <= r:  # 如果左小于等于右
            m = (l + r) // 2
            if arr[i] > ends[m]:  # 二分法查找，查找元素在ends里的位置
                l = m + 1  # 如果比查找点大，左点移动
            else:
                r = m - 1  # 如果比查找点小，右点移动
        right = max(right, l)  # 下次查找的右点
        ends[l] = arr[i]  # 赋值新的序列值
        dp[i] = l + 1  # 因为是按排序的，所有左右只有一边点不停移动，l是新点在ends的位置，l从0开始，所以加1
    return dp


def generateLIS2(arr):
    dp = getdp2(arr)
    n = max(dp)
    index = dp.index(n)  # 获取最大值的序号
    lis = [0] * n
    n -= 1  # 因为列表从0开始，所有n减1
    lis[n] = arr[index]  # 将子序列末尾的序号赋值
    # 从右向左
    for i in range(index, - 1, -1):
        # 关键
        if arr[i] < arr[index] and dp[i] == dp[index] - 1:  # 如果序列的值小于末尾值，且编号为末尾序号减1
            n -= 1
            lis[n] = arr[i]  # 赋值给列表
            index = i  # 序号为该i
    return lis