首页 > 试题广场 >

最长上升子序列

[编程题]最长上升子序列

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

广场上站着一支队伍，她们是来自全国各地的扭秧歌代表队，现在有她们的身高数据，请你帮忙找出身高依次递增的子序列。例如队伍的身高数据是（1、7、3、5、9、4、8），其中依次递增的子序列有（1、7），（1、3、5、9），（1、3、4、8）等，其中最长的长度为4。

输入描述:

输入包含多组数据，每组数据第一行包含一个正整数n（1≤n≤1000）。

紧接着第二行包含n个正整数m（1≤n≤10000），代表队伍中每位队员的身高。

输出描述:

对应每一组数据，输出最长递增子序列的长度。

示例1

输入

7
1 7 3 5 9 4 8
6
1 3 5 2 4 6

输出

4
4

算法知识视频讲解

Python

TimeMac

Python自实现时间复杂度O（nlogn）

创建一个数组subSeries，数组保存着0~i 的当前子序列最长的上升序列最后一个数的最小数

（每个位置放着比下标大一的上升子序列长度中的最后一个（也是相同长度的最小值））

可以输出观察

如果该数组有记录的话,如果你比该数组的最后一个数大的话，把该数添加到辅助数组中，最大递增子序列加一

否则在里面查找到比你大的最小数的前面替换掉，在数组的下标其实就是以该数结尾的最长子序列长度

try:
    while True:
        num,digitsList = int(input()),list(map(int,input().split()))
        subSeries = []
        maxLen = 0
        subSeries.append(digitsList[0])  #辅助数组
        for i in range(1,num):
            if digitsList[i] > subSeries[maxLen]:
                maxLen += 1
                subSeries.append(digitsList[i])
            else:
                left,right = 0,maxLen
                while left <= right:    #在已有的subSeries数组范围内二分查找到比该数大的最小数替换掉
                    mid = (left+right)//2
                    if digitsList[i] > subSeries[mid]:
                        left = mid+1
                    else:
                        right = mid-1
                subSeries[left] = digitsList[i]
    #        print(" ".join(map("{:>2}".format, subSeries)))  #每次打印出来观察
        print(maxLen+1)
except Exception:
    pass

编辑于 2018-09-23 22:44:20 回复(0)

Python

华科平凡

烂大街的题目。python解法，时间复杂度nlogN

import bisect

while True:
    try:
        a, b = input(), map(int, input().split())
        q = []
        for i in b:
            pos = bisect.bisect_left(q, i)
            if pos == len(q):
                q.append(i)
            else:
                q[pos] = i
        print(len(q))
    except:
        break

发表于 2017-10-11 15:15:13 回复(1)