最长递增子序列

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

热度指数：12814 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

对于一个数字序列，请设计一个复杂度为O(nlogn)的算法，返回该序列的最长上升子序列的长度，这里的子序列定义为这样一个序列U1，U2...，其中Ui < Ui+1，且A[Ui] < A[Ui+1]。

给定一个数字序列A及序列的长度n，请返回最长上升子序列的长度。

测试样例：

[2,1,4,3,1,5,6],7

返回：4

算法知识视频讲解

查看答案及解析

Python

离疏

# -*- coding:utf-8 -*-
import bisect #二分搜索模块
class AscentSequence:
    def findLongest(self, A, n):
        res=[]
        for i in A:
            pos=bisect.bisect_left(res,i)#在res中查找i，i存在时返回i左侧的位置，i不存在返回应该插入的位置
            if pos==len(res): #如果当前数比res中最后一个数还大，直接添加
                res.append(i)
            else: #否则，找到替换位置替换原来的数
                res[pos]=i
        return len(res)

发表于 2018-08-13 14:31:18 回复(0)

Python

教练，我可能想谈恋爱了

打印出最长递增子序列：

# -*- coding:utf-8 -*-
class AscentSequence:
    def findLongest(self, A, n):
        out=[[A[0]]]
        max_out=[A[0]]
        for i in range(1,len(A)):
            if max_out[-1]<=A[i]:
                out.append(max_out+[A[i]])
                max_out=out[-1]
            else:
                l=0
                flag=0
                for j in range(i - 1, -1, -1):
                    if out[j][-1]<=A[i]:
                        if l==0:
                            out.append(out[j] + [A[i]])
                            l = len(out[-1])
                            flag = 1
                        elif l<=len(out[j]+[A[i]]):
                            l=len(out[j]+[A[i]])
                            out.pop(-1)
                            out.append(out[j]+[A[i]])
                            flag=1
                if flag==0:
                    out.append([A[i]])
                if len(max_out) <= len(out[-1]):
                    max_out = out[-1]
        return len(max_out)

发表于 2018-07-03 21:49:13 回复(0)

Python

杨云同学

class AscentSequence:
    def findLongest(self, A, n):
        L = [1]*len(A)
        for c, v in enumerate(A):
            for i in range(c):
                if A[i] <= v: L[c] = max(L[c], 1+L[i])
        return max(L)

发表于 2018-04-19 10:40:17 回复(0)

Python

offer到碗里

class AscentSequence:
    def findLongest(self, A, n):
        # write code here
        dp = [0]*n
        dp[0]= 1
        for i in range(1,len(A)):
            l = [1]
            for j in range(0,i):
                if A[i]>A[j]:
                    l.append(dp[j]+1)
            dp[i] = max(l)
        return max(dp)

发表于 2018-01-24 12:01:09 回复(0)

Python

华科平凡

python只需要6行代码搞定，不多bb：

import bisect
class AscentSequence:
    def findLongest(self, A, n):

        res=[]
        for i in A:
            pos=bisect.bisect_left(res,i)
            if pos==len(res): res.append(i)
            else: res[pos]=i
        return len(res)

编辑于 2017-09-16 17:58:56 回复(0)