首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >求最长子序列的长度

问求最长子序列的长度
EN

Stack Overflow用户
提问于 2019-12-22 23:47:17
回答 1查看 116关注 0票数 0

这里,在这段代码中,它打印一个序列的最大子序列的长度,该序列先增后减,反之亦然。

例如:

输入: 1,11,2,10,4,5,2,1

输出:6(长度为6的最长子序列是1,2,10,4,2,1)

但是我如何让它在三个单调(递增或递减)的区域中工作呢?

像增加-减少-增加或减少-增加-减少

示例:

输入:7 16 1 6 20 17 7 18 25 1 25 21 11 5 29 11 3 3 26 19

输出: 12

(最大的子序列:7 1 6 17 18 25 25 21 11 5 33)如我们所见,

分为7、1/6、17、18、25、25/21、11、5、3、3三个区域

代码语言:javascript
复制
arr = list(map(int, input().split()))
def lbs(arr): 
    n = len(arr) 

    lis = [1 for i in range(n+1)] 

    for i in range(1 , n): 
        for j in range(0 , i): 
            if ((arr[i] > arr[j]) and (lis[i] < lis[j] +1)): 
                lis[i] = lis[j] + 1


    lds = [1 for i in range(n+1)] 

    for i in reversed(range(n-1)):
        for j in reversed(range(i-1 ,n)):  
            if(arr[i] > arr[j] and lds[i] < lds[j] + 1): 
                lds[i] = lds[j] + 1 



    maximum = lis[0] + lds[0] - 1
    for i in range(1 , n): 
        maximum = max((lis[i] + lds[i]-1), maximum) 

    return maximum 

print ("Length of LBS is",lbs(arr)) 
EN

回答 1

Stack Overflow用户

发布于 2019-12-23 09:50:21

我想出了一个O(n^2logn)的想法。

您希望将整个片段分为三个部分:第一部分包含递增的子序列,第二部分包含递减的子序列,最后一部分包含再次递增的子序列。

首先,让我们选择一个序列的前缀-第一部分(O(n)可能性)。为了最小化检查间隔的数量,您可以只选择最后一个元素在其最长递增子序列中的前缀。(换句话说,当选择范围1,x时,a_x应该在它最长的递增子序列中)

现在你有了与你已经解决的问题类似的问题-寻找递减,然后递增的子序列(顺便说一句,我会使用二进制搜索而不是你使用的for循环)。唯一不同的是,递减的子序列必须从小于所选前缀的最后一个元素的值开始(忽略任何大于或等于的值)-您可以在O(n log n)中这样做。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/59445681

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档