-1

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

这是我的 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) 时间内完成？

4

1 回答 1

2

评论中提到了很多资源；如果您仍然想要一段 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
于 2016-07-02T15:25:37.760 回答