增长最快的子序列

Question

给定输入序列,找到最长(不一定是连续的)非递减子序列的最佳方法是什么.

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)

我正在寻找最好的算法.如果有代码,Python会很好,但一切都没问题.

Answer 1

我只是偶然发现了这个问题,并提出了这个Python 3实现:

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

由于花了一些时间来理解算法是如何工作的,我对评论有点冗长,我还会添加一个快速解释:

• seq 是输入序列.
• L 是一个数字:它在循环序列时得到更新,它标记到那个时刻发现的最长的后续子序列的长度.
• M是一个清单.M[j-1]将指向一个索引,seq该索引包含可用于(最后)的最小值,以构建增加的长度子序列j.
• P是一个清单.P[i]将指向M[j],i指数在哪里seq.简而言之,它告诉哪个是子序列的前一个元素.P用于在最后构建结果.

算法如何工作:

1. 处理空序列的特殊情况.
2. 从1个元素的子序列开始.
3. 用索引循环输入序列i.
4. 用二进制搜索发现j,让seq[M[j]有<比seq[i].
5. 更新P,M和L.
6. 追溯结果并将其反转.

注意:与维基百科算法的唯一区别是M列表中的偏移量为1,X这里称为seq.我还用Eric Gustavson回答的一个稍微改进的单元测试版测试了它,它通过了所有的测试.

例:

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

       0    1   2   3   4   5   6   <-- indexes

最后,我们将:

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

正如你所看到P的那样非常简单.我们来看看它到底,所以它告诉之前60还有的40,前80有40,以前40有20,之前50有20和以前20有10,停下来.

复杂的部分是开启的M.在开头M是[0, None, None, ...]因为长度为1的子序列的最后一个元素(因此位置0 in M)位于索引0 : 30.

在这一点上,我们将开始循环上seq看看10,既然10是<比30,M将被更新:

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

所以现在M看起来像:[1, None, None, ...].这是一件好事,因为10有更多的椅子来创造一个更长的增长子序列.(新1是10的指数)

现在轮到了20.使用10和20我们有长度为2的索引(索引1 in M),所以M将是:[1, 2, None, ...].(新2是20的指数)

现在轮到了50.50将不会成为任何子序列的一部分,所以没有任何变化.

现在轮到了40.用10,20并且40我们在长度为3(索引2的子M,所以M将是:[1, 2, 4, None, ...](新图4是40指数)

等等...

要完整浏览代码,您可以将其复制并粘贴到此处 :)

Answer 2

以下是如何在Mathematica中找到最长的增加/减少子序列:

 LIS[list_] := LongestCommonSequence[Sort[list], list];
 input={0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
 LIS[input]
 -1*LIS[-1*input]

输出:

{0, 2, 6, 9, 11, 15}
{12, 10, 9, 5, 3}

Mathematica 在Combinatorica`库中也有LongestIncreasingSubsequence函数.如果您没有Mathematica,可以查询WolframAlpha.

C++ O(nlogn)解决方案

根据一些观察,还有一个O(nlogn)解决方案.令Ai,j是使用元素a ₁,a ₂,...,a _i的所有增加的长度为j的子序列中的最小可能尾部.观察到,对于任何特定的i,A _i,1,A _i,2,...,A _i,j.这表明如果我们想要以ai + 1结尾的最长子序列,我们只需要寻找aj,使得Ai,j <ai + 1 <= Ai,j + 1并且长度将是j + 1.注意在这种情况下,Ai + 1,j + 1将等于ai + 1,并且对于k!= j + 1,所有Ai + 1,k将等于Ai,k.此外,集合Ai和集合Ai + 1之间至多存在一个差异,这是由该搜索引起的.由于A总是按递增顺序排序,并且操作不会改变这种排序,我们可以对每个单独的a ₁,a ₂,...,a _n进行二进制搜索.

实现C++(O(nlogn)算法)

#include <vector>
using namespace std;

/* Finds longest strictly increasing subsequence. O(n log k) algorithm. */
void find_lis(vector<int> &a, vector<int> &b)
{
  vector<int> p(a.size());
  int u, v;

  if (a.empty()) return;

  b.push_back(0);

  for (size_t i = 1; i < a.size(); i++) {
      if (a[b.back()] < a[i]) {
          p[i] = b.back();
          b.push_back(i);
          continue;
      }

      for (u = 0, v = b.size()-1; u < v;) {
          int c = (u + v) / 2;
          if (a[b[c]] < a[i]) u=c+1; else v=c;
      }

      if (a[i] < a[b[u]]) {
          if (u > 0) p[i] = b[u-1];
          b[u] = i;
      }   
  }

  for (u = b.size(), v = b.back(); u--; v = p[v]) b[u] = v;
}

/* Example of usage: */
#include <cstdio>
int main()
{
  int a[] = { 1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 };
  vector<int> seq(a, a+sizeof(a)/sizeof(a[0]));
  vector<int> lis;
        find_lis(seq, lis);

  for (size_t i = 0; i < lis.size(); i++)
      printf("%d ", seq[lis[i]]);
        printf("\n");    

  return 0;
}

来源:链接

我刚刚将C++实现改写为Java,并且可以确认它是否有效.python中的矢量替代是List.但是如果你想自己测试一下,这里是在线编译器的链接,加载了示例实现:link

示例数据是:{ 1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 } 并回答:1 3 4 5 6 7.