求最长子序列的长度

Question

这里，在这段代码中，它打印序列的最大子序列的长度，该序列先增加后减少，或者反之亦然。

例如：

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

如增-减-增或减-增-减

示例：

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

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)) 

Answer 1

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

您希望将整个段分成三部分：第一部分包含递增子序列，第二部分包含递减子序列，最后一部分包含递增子序列。

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