最长递增子序列（LCS）

[编程题]最长递增子序列（LCS）

热度指数：2413 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

给定一个序列 An = a1 ,a2 , ... , an ，找出最长的子序列使得对所有 i < j ，ai < aj 。求出这个子序列的长度

输入描述:

输入的序列

输出描述:

最长递增子序列的长度

示例1

输入

1 -1 2 -2 3 -3 4

输出

算法知识视频讲解

Python

华科平凡

python：

提供两种解法。

第一种是正常的动态规则：

LIS是一个数组，里面维护的是每个位置最长上升子序列的值。在遍历数组的过程中，对应位置的LIS[i]都会得到更新，时间复杂度为O(n^2)。

def lengthOfLIS(nums):
    if not nums: return 0
    LIS = [1] * len(nums)
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[i] > nums[j] and  LIS[i] < LIS[j] + 1:
                    LIS[i] = LIS[j] + 1
    return max(LIS)

print(lengthOfLIS(list(map(int, input().split()))))

也可以使用bisect模块，可以调试一下，观察每一步的变化：

import bisect

def lengthOfLIS(nums):
    q=[]
    for v in nums:
        pos=bisect.bisect_left(q,v)
        if pos==len(q):
            q.append(v)
        else:
            q[pos]=v
    return len(q)

print(lengthOfLIS(map(int,input().split())))

发表于 2019-03-19 22:45:02 回复(0)