首页 > 试题广场 >

最长上升子序列(三)

[编程题]最长上升子序列(三)
  • 热度指数：75293 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定数组 arr ，设长度为 n ，输出 arr 的最长上升子序列。（如果有多个答案，请输出其中 按数值(注：区别于按单个字符的ASCII码值)进行比较的 字典序最小的那个）

数据范围：
要求：空间复杂度 ，时间复杂度
示例1

输入

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

输出

[1,3,4,8,9]
示例2

输入

[1,2,8,6,4]

输出

[1,2,4]

说明

其最长递增子序列有3个，（1，2，8）、（1，2，6）、（1，2，4）其中第三个 按数值进行比较的字典序 最小，故答案为（1，2，4）

备注:

算法知识视频讲解
添加回答
Python 3
yusei_ooo头像 yusei_ooo 
#
# retrun the longest increasing subsequence
# @param arr int整型一维数组 the array
# @return int整型一维数组
#
class Solution:
    def LIS(self , arr ):
        # write code here
#       动态规划，超时，加入maxEnd记录
        if len(arr)<2:
            return arr
        def biSearch(l,r,target,arr):
            while(l<r):
                mid = l+(r-l)//2
                if arr[mid]<=target:
                    l = mid+1
                else:
                    r = mid
            if l == len(arr):
                return l-1
            return l
        n = len(arr)
        dp = [1]*n
        idx = 0
        res = 0
        maxEnd=[arr[0]] # 长度为i+1的子序列最小尾元素
        for i in range(1,n):
            if maxEnd[-1]<arr[i]:
                dp[i] = len(maxEnd)+1
                maxEnd.append(arr[i])
            else:
                idx = biSearch(0,len(maxEnd),arr[i],maxEnd)
                maxEnd[idx] = arr[i]
                dp[i] = idx+1
        ans = []
        res = len(maxEnd)
        for i in range(n-1,-1,-1):
            if res==0:
                break
            if dp[i] == res:
                ans.append(arr[i])
                res-=1
        return ans[::-1]
            
        

发表于 2021-09-28 15:27:44 回复(0)
Python 3
牛客38477449号头像 牛客38477449号 
#
# retrun the longest increasing subsequence
# @param arr int整型一维数组 the array
# @return int整型一维数组
#
class Solution:
    def LIS(self , arr ):
        # write code here
        if len(arr) < 2:
            return arr
        dp = [arr[0]]
        maxlen = [1]
        for i in range(1, len(arr)):
            if arr[i] > dp[-1]:
                dp.append(arr[i])
                maxlen.append(len(dp))
            else:
                pos = self.binary_search(dp, arr[i])
                dp[pos] = arr[i]
                maxlen.append(pos+1)
        i = len(maxlen) - 1
        j = len(dp)
        while i >= 0:
            if maxlen[i] == j:
                j -= 1
                dp[j] = arr[i]
            i -= 1
        return dp
                
                
    def binary_search(self, dp, num):
        low, high = 0, len(dp) - 1
        while low <= high:
            mid = low + ((high - low) >> 1)
            if dp[mid] == num:
                return mid
            elif dp[mid] > num:
                high = mid - 1
            else:
                low = mid + 1
        return low

发表于 2021-09-13 18:05:05 回复(0)
Python 3
12枚硬币头像 12枚硬币 
class Solution:
    # 二分法 同时得到动态规划中以每个元素结尾最长子升序列长度的列表dp
    def LIS(self, arr):
 
        # 不同长度递增序列的末尾元素，取最小值。
        # 如5 2 6 1 7的三种长度子序列为[1] [2,6] [2,6,7],取末尾tails=[1,6,7]
        # tails的长度是最长递增子序列长度
        tails = [arr[0]]
        # 每个位置上，以该元素结尾的最长递增子序列长度，和动态规划中dp相同
        len_list = [1] * len(arr)
        max_len = 1
        # 二分法找每个元素在tails中的位置，替换最接近且小于它的元素，若最大接在后面
        for i in range(1,len(arr)):
            l, r = 0, len(tails)
            # i中值加1不可能大于j，退出时必然i=j
            while l < r:
                m = (l + r) // 2
                if tails[m] < arr[i]:
                    l = m + 1
                else:r = m
            if l == len(tails):
                tails.append(arr[i])
                max_len += 1
            else:
                tails[l] = arr[i]
            len_list[i] = l+1
 
        res = []
        # 相同长度的子序列，后面的值小，否则若值大可以构成更长序列。
        # 所以每个长度len在len+1出现前的最后一个位置，这个位置的值是结果中第len个
        # 例如      5   2    6   1   7
        # len_list  1  [1]  [2]  1  [3]       结果 [2, 6, 7]
        for i in range(len(arr) - 1, -1, -1):
            if max_len == 0:
                break
            if len_list[i] == max_len:
                res.append(arr[i])
                max_len -= 1
        return res[::-1]

发表于 2021-09-02 23:37:07 回复(0)
Python 3
反向平行排列头像 反向平行排列
感谢华科不平凡提供的贪心算法+二分查找以及如何寻找靠前子序列的思路，特奉上python3代码方便大家
#
# retrun the longest increasing subsequence
# @param arr int整型一维数组 the array
# @return int整型一维数组
#
import bisect
class Solution:
    def LIS(self , arr ):
        # write code here
        def tool(target):
            left = 0
            right = len(data)-1
            while left<=right:
                mid = left+(right-left)//2
                if data[mid]==target:
                    return mid
                elif data[mid]>target:
                    right = mid-1
                else:
                    left = mid+1
            return left
        data = [arr[0]]
        n = len(arr)
        max_len =[1]
        for i in range(1,n):
            if data[-1]<arr[i]:
                data.append(arr[i])
                max_len.append(len(data))
            else:
                temp = tool(arr[i])
                data[temp] = arr[i]
                max_len.append(temp+1)
        maxs = len(data)
        for i in range(len(arr)-1,-1,-1):
            if maxs == max_len[i]:
                data[maxs-1] = arr[i]
                maxs-=1
        return data

发表于 2021-08-16 10:49:45 回复(0)
Python 3
miliang_8421头像 miliang_8421
import bisect

class Solution(object):
    def LIS(self,arr):
        cache = []
        max_len = [] 
        for i in arr:
            index = bisect.bisect_left(cache,i)
            if len(cache) == index:
                cache.append(i)
            else:
                cache[index] = i
            max_len.append(index+1)
        res_length = len(cache)
        res = []
        for index in range(len(arr)-1,-1,-1):
            if max_len[index] == res_length:
                res.insert(0,arr[index])
                res_length -=1
    
        return res
        
发表于 2021-08-13 15:53:05 回复(0)
Python 3
找工作的Amber还是个孩子TT头像 找工作的Amber还是个孩子TT 
class Solution:
    def LIS(self , arr ):
        n = len(arr)
        dp = [[],[10e9]]
        num = 1
        import copy
        for j in range(n):
            for i in range(1,num + 1):
                if dp[i-1]==[]&nbs***bsp;(dp[i-1]!=[] and dp[i-1][-1]<arr[j]):
                        temp = copy.copy(dp[i - 1])
                        temp.append(arr[j])
                        if sum(temp) < sum(dp[i]):
                            dp[i]=temp
                            num1 = max(num, i+1)
            num=num1
            dp.append([10e9]*(num))
        return(dp[num-1])
为什么会超时呢？？？？？

发表于 2021-07-26 01:05:53 回复(0)
Python 3
蓝猫小哥哥头像 蓝猫小哥哥 
#
# retrun the longest increasing subsequence
# @param arr int整型一维数组 the array
# @return int整型一维数组
#
import bisect
class Solution:
    def LIS(self , arr ):
        # write code here
        '''
        先求arr每一个数对应在最长递增子序列中的index，或者说，求添加了arr[i]后，递增子序列的长度。
        （即求最长递增子序列的长度）
        然后根据这个index填充最长递增子序列。
        '''
        array,maxlen = [],[]
        for i in range(len(arr)):
            if not array:
                array.append(arr[i])
                maxlen.append(len(array))
            else:
                if arr[i] > array[-1]:
                    array.append(arr[i])
                    maxlen.append(len(array))
                else:
                    idx = bisect.bisect_left(array, arr[i])
                    array[idx] = arr[i]
                    maxlen.append(idx+1)
                    
        j = len(array)-1
        for i in range(len(arr)-1,-1,-1):
            if j < 0:break
            if maxlen[i]==j+1:
                array[j] = arr[i]
                j-=1
        return array
            
        

发表于 2021-07-20 20:43:56 回复(0)
提交观点

问题信息

动态规划 二分
难度：
12条回答 15054浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号