这里,在这段代码中,它打印一个序列的最大子序列的长度,该序列先增后减,反之亦然。
例如:
输入: 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三个区域
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)) 发布于 2019-12-23 09:50:21
我想出了一个O(n^2logn)的想法。
您希望将整个片段分为三个部分:第一部分包含递增的子序列,第二部分包含递减的子序列,最后一部分包含再次递增的子序列。
首先,让我们选择一个序列的前缀-第一部分(O(n)可能性)。为了最小化检查间隔的数量,您可以只选择最后一个元素在其最长递增子序列中的前缀。(换句话说,当选择范围1,x时,a_x应该在它最长的递增子序列中)
现在你有了与你已经解决的问题类似的问题-寻找递减,然后递增的子序列(顺便说一句,我会使用二进制搜索而不是你使用的for循环)。唯一不同的是,递减的子序列必须从小于所选前缀的最后一个元素的值开始(忽略任何大于或等于的值)-您可以在O(n log n)中这样做。
https://stackoverflow.com/questions/59445681
复制相似问题