最长递增子序列优化

Question

最长递增子序列问题是找到给定序列的子序列，其中子序列的元素按排序顺序排列，并且子序列尽可能长。

这是我的 O(n^2) 方法，它运行对于长输入非常慢：

N = int(input())

lst = []
for i in range(N):
    lst.append(input())

count = [1] * N

for i in range(1, len(lst)):
    for j in range(i):
        if(int(lst[j]) < int(lst[i])):
            k = int(count[j]) + 1
            if (k > int(count[i])):
                count[i] = k
count.sort()
print(count[-1])

谁能告诉我如何在 O(n*log n) 时间内完成？

Answer 1

评论中提到了很好的资源；如果您还想要一段 python 代码，我已经在此处编写并进行了解释。

在此算法中，对于所有 L < N，我们跟踪输入中的值，这些值表示当前最长递增子序列长度 L.

的端点

longest_sequence_values 存储这些值。例如，longest_sequence_values[3] 是输入中长度为 3 的最长递增子序列结束处的值。

注意这里 longest_sequence_values 将始终是非递减的，这允许我们在尝试构建新的最长递增子序列时执行二分查找。发生这种情况是因为如果 i < j，则长度 i 的子序列的端点不能大于长度 j.

的子序列的端点

longest_current_sequence 是迄今为止找到的最长子序列的长度。我们需要这个值来指定二分查找的范围。也代表了最后的答案。

from math import ceil
N = int(input())

input_vals = []
for i in range(N):
    input_vals.append(input())

longest_sequence_values = [None] * (N+1)
longest_current_sequence = 0

for i in range(N):
    # binary search starts here
    # this gives us the log(N) factor
    lo = 1
    hi = longest_current_sequence
    while lo <= hi:
        mid = int(ceil((lo+hi)/2))
        if longest_sequence_values[mid] <= input_vals[i]:
            lo = mid + 1
        else:
            hi = mid - 1

    # lo will be length of the longest sequence ending at input_vals[i]
    longest_len_here = lo
    # We have a new lis of length longest_len_here ending at index i
    # Note that before we perform the following substitutions,
    # longest_sequence_values[longest_len_here] >= input_vals[i]
    # This means that the new endpoint of the lis of length longest_len_here
    # is <= to the old endpoint.
    # This point is essential in keeping the result optimal
    longest_sequence_values[longest_len_here] = input_vals[i]

    if longest_len_here > longest_current_sequence:
        longest_current_sequence = longest_len_here

print longest_current_sequence

最长递增子序列优化

Longest Increasing Subsequence optimization

python

dynamic-programming

subsequence