由网友(眉眼如初风华如故)分享简介：给定输入序列，什么是找到最长（不一定连续）非递减序列的最佳方式。Given an input sequence, what is the best way to find the longest (not necessarily continuous) non-decreasing subsequence.0, 8...

给定输入序列，什么是找到最长（不一定连续）非递减序列的最佳方式。

Given an input sequence, what is the best way to find the longest (not necessarily continuous) non-decreasing subsequence.

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 # sequence

1, 9, 13, 15 # non-decreasing subsequence

0, 2, 6, 9, 13, 15 # longest non-deceasing subsequence (not unique)

我在寻找最好的算法。如果有code，Python的将是很好的，但任何事情都是正常的。

I'm looking for the best algorithm. If there is code, Python would be nice, but anything is alright.

推荐答案

我只是偶然在这个问题上，并想出了这个Python 3的实现：

I just stumbled in this problem, and came up with this Python 3 implementation:

def subsequence(seq):
    if not seq:
        return seq

    M = [None] * len(seq)    # offset by 1 (j -> j-1)
    P = [None] * len(seq)

    # Since we have at least one element in our list, we can start by 
    # knowing that the there's at least an increasing subsequence of length one:
    # the first element.
    L = 1
    M[0] = 0

    # Looping over the sequence starting from the second element
    for i in range(1, len(seq)):
        # Binary search: we want the largest j <= L
        #  such that seq[M[j]] < seq[i] (default j = 0),
        #  hence we want the lower bound at the end of the search process.
        lower = 0
        upper = L

        # Since the binary search will not look at the upper bound value,
        # we'll have to check that manually
        if seq[M[upper-1]] < seq[i]:
            j = upper

        else:
            # actual binary search loop
            while upper - lower > 1:
                mid = (upper + lower) // 2
                if seq[M[mid-1]] < seq[i]:
                    lower = mid
                else:
                    upper = mid

            j = lower    # this will also set the default value to 0

        P[i] = M[j-1]

        if j == L or seq[i] < seq[M[j]]:
            M[j] = i
            L = max(L, j+1)

    # Building the result: [seq[M[L-1]], seq[P[M[L-1]]], seq[P[P[M[L-1]]]], ...]
    result = []
    pos = M[L-1]
    for _ in range(L):
        result.append(seq[pos])
        pos = P[pos]

    return result[::-1]    # reversing

因为我花了一些时间来了解该算法的工作我有点冗长与意见，我还将添加一个快速的解释：

Since it took me some time to understand how the algorithm works I was a little verbose with comments, and I'll also add a quick explanation:

序列是输入序列。 →是一个数字：它被更新，而遍历序列，它标志着最长incresing子发现了那一刻的长度 M 是一个列表。 M [J-1] 将指向指数序列保存，可用于最小的值（结束）建设长度的递增子Ĵ。 P 是一个列表。 P [I] 将指向 M [J] ，其中我是序列的索引。在几句话，它告诉这是序​​列的previous元素。 P 用于在年底打造的结果。 seq is the input sequence. L is a number: it gets updated while looping over the sequence and it marks the length of longest incresing subsequence found up to that moment. M is a list. M[j-1] will point to an index of seq that holds the smallest value that could be used (at the end) to build an increasing subsequence of length j. P is a list. P[i] will point to M[j], where i is the index of seq. In a few words, it tells which is the previous element of the subsequence. P is used to build the result at the end.

算法如何工作的：

在处理一个空序列的特殊情况。 在开始用1元的序列。 在遍历索引输入序列我。 使用二进制搜索找到Ĵ让序列[M [J] 是＆LT; 比序列[I] 更新 P ， M 和→。 回溯的结果，并返回它扭转。 Handle the special case of an empty sequence. Start with a subsequence of 1 element. Loop over the input sequence with index i. With a binary search find the j that let seq[M[j] be < than seq[i]. Update P, M and L. Traceback the result and return it reversed.

注意：的维基算法1 是偏移唯一的区别在 M 列表，以及 X 在此被称为序列。我也用了一个稍微改进单元测试版的测试显示，埃里克克古斯达夫逊答案并通过了所有的测试。

Note: The only differences with the wikipedia algorithm are the offset of 1 in the M list, and that X is here called seq. I also test it with a slightly improved unit test version of the one showed in Eric Gustavson answer and it passed all tests.

例如：

seq = [30, 10, 20, 50, 40, 80, 60]

       0    1   2   3   4   5   6   <-- indexes

最后，我们将有：

At the end we'll have:

M = [1, 2, 4, 6, None, None, None]
P = [None, None, 1, 2, 2, 4, 4]
result = [10, 20, 40, 60]

您将看到 P 是pretty的简单。我们来看看它到底，所以它告诉前 60 有 40 在 80 有 40 ，在 40 有 20 ，在 50 有 20 和前 20 有 10 ，停止。

As you'll see P is pretty straightforward. We have to look at it from the end, so it tells that before 60 there's 40,before 80 there's 40, before 40 there's 20, before 50 there's 20 and before 20 there's 10, stop.

这个复杂的部分是 M 。在开始的时候 M 是 [0，无，无，...] 自的子序列的最后一个元素长度1（在 M 因此位置0）是该指数在0： 30 。

The complicated part is on M. At the beginning M was [0, None, None, ...] since the last element of the subsequence of length 1 (hence position 0 in M) was at the index 0: 30.

在这一点上，我们将开始循环对序列看看 10 ，因为 10 是＆LT; 比 30 ， M 将被更新：

At this point we'll start looping on seq and look at 10, since 10 is < than 30, M will be updated:

if j == L or seq[i] < seq[M[j]]:
    M[j] = i

所以，现在 M 是这样的： [1，无，无，...] 。这是一件好事，因为 10 有更多chanches创建一个较长的递增子。 （新1是10的指数）

So now M looks like: [1, None, None, ...]. This is a good thing, because 10 have more chanches to create a longer increasing subsequence. (The new 1 is the index of 10)

现在它的转弯 20 。随着 10 和 20 我们有长度2（索引1的中号子），所以 M 将是： [1，2，无，...] 。 （新的2是20的指数）

Now it's the turn of 20. With 10 and 20 we have subsequence of length 2 (index 1 in M), so M will be: [1, 2, None, ...]. (The new 2 is the index of 20)

现在它的转弯 50 。 50 不会那么没有任何变化序列的组成部分。

Now it's the turn of 50. 50 will not be part of any subsequence so nothing changes.

现在它的转弯 40 。随着 10 ， 20 和 40 我们有一子长度3（索引2 M ，所以 M 将是： [1，2， 4，无，...] 。（新4是40的指数）

Now it's the turn of 40. With 10, 20 and 40 we have a sub of length 3 (index 2 in M, so M will be: [1, 2, 4, None, ...] . (The new 4 is the index of 40)

等等...

有关通过code一个完整的步行路程，您可以复制并粘贴这里：）

For a complete walk through the code you can copy and paste it here :)