最长的递增子序列

Question

给定输入序列，找到最长（不一定连续）非递减子序列的最佳方法是什么。0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 # sequence1, 9, 13, 15 # non-decreasing subsequence0, 2, 6, 9, 13, 15 # longest non-deceasing subsequence (not unique)我正在寻找最佳算法。如果有代码，Python会很好，但是一切都很好。

Answer 1

这是一个相当通用的解决方案：

O(n log n)及时运行

处理增加，减少，减少和增加的子序列，

与任何序列对象，包括工程list，numpy.array，str多，

通过key参数（类似于内置sorted函数中的参数）支持对象列表和自定义比较方法，

可以返回子序列的元素或其索引。

编码：

from bisect import bisect_left, bisect_right

from functools import cmp_to_key

def longest_subsequence(seq, mode='strictly', order='increasing',

                        key=None, index=False):

  bisect = bisect_left if mode.startswith('strict') else bisect_right

  # compute keys for comparison just once

  rank = seq if key is None else map(key, seq)

  if order == 'decreasing':

    rank = map(cmp_to_key(lambda x,y: 1 if x<y else 0 if x==y else -1), rank)

  rank = list(rank)

  if not rank: return []

  lastoflength = [0] # end position of subsequence with given length

  predecessor = [None] # penultimate element of l.i.s. ending at given position

  for i in range(1, len(seq)):

    # seq[i] can extend a subsequence that ends with a lesser (or equal) element

    j = bisect([rank[k] for k in lastoflength], rank[i])

    # update existing subsequence of length j or extend the longest

    try: lastoflength[j] = i

    except: lastoflength.append(i)

    # remember element before seq[i] in the subsequence

    predecessor.append(lastoflength[j-1] if j > 0 else None)

  # trace indices [p^n(i), ..., p(p(i)), p(i), i], where n=len(lastoflength)-1

  def trace(i):

    if i is not None:

      yield from trace(predecessor[i])

      yield i

  indices = trace(lastoflength[-1])

  return list(indices) if index else [seq[i] for i in indices]

我为上面没有粘贴的函数编写了一个文档字符串，以展示代码：

"""

Return the longest increasing subsequence of `seq`.

Parameters

----------

seq : sequence object

  Can be any sequence, like `str`, `list`, `numpy.array`.

mode : {'strict', 'strictly', 'weak', 'weakly'}, optional

  If set to 'strict', the subsequence will contain unique elements.

  Using 'weak' an element can be repeated many times.

  Modes ending in -ly serve as a convenience to use with `order` parameter,

  because `longest_sequence(seq, 'weakly', 'increasing')` reads better.

  The default is 'strict'.

order : {'increasing', 'decreasing'}, optional

  By default return the longest increasing subsequence, but it is possible

  to return the longest decreasing sequence as well.

key : function, optional

  Specifies a function of one argument that is used to extract a comparison

  key from each list element (e.g., `str.lower`, `lambda x: x[0]`).

  The default value is `None` (compare the elements directly).

index : bool, optional

  If set to `True`, return the indices of the subsequence, otherwise return

  the elements. Default is `False`.

Returns

-------

elements : list, optional

  A `list` of elements of the longest subsequence.

  Returned by default and when `index` is set to `False`.

indices : list, optional

  A `list` of indices pointing to elements in the longest subsequence.

  Returned when `index` is set to `True`.

"""

一些例子：

>>> seq = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]

>>> longest_subsequence(seq)

[0, 2, 6, 9, 11, 15]

>>> longest_subsequence(seq, order='decreasing')

[12, 10, 9, 5, 3]

>>> txt = ("Given an input sequence, what is the best way to find the longest"

               " (not necessarily continuous) non-decreasing subsequence.")

>>> ''.join(longest_subsequence(txt))

' ,abdegilnorsu'

>>> ''.join(longest_subsequence(txt, 'weak'))

'              ceilnnnnrsssu'

>>> ''.join(longest_subsequence(txt, 'weakly', 'decreasing'))

'vuutttttttssronnnnngeee.'

>>> dates = [

...   ('2015-02-03', 'name1'),

...   ('2015-02-04', 'nameg'),

...   ('2015-02-04', 'name5'),

...   ('2015-02-05', 'nameh'),

...   ('1929-03-12', 'name4'),

...   ('2023-07-01', 'name7'),

...   ('2015-02-07', 'name0'),

...   ('2015-02-08', 'nameh'),

...   ('2015-02-15', 'namex'),

...   ('2015-02-09', 'namew'),

...   ('1980-12-23', 'name2'),

...   ('2015-02-12', 'namen'),

...   ('2015-02-13', 'named'),

... ]

>>> longest_subsequence(dates, 'weak')

[('2015-02-03', 'name1'),

 ('2015-02-04', 'name5'),

 ('2015-02-05', 'nameh'),

 ('2015-02-07', 'name0'),

 ('2015-02-08', 'nameh'),

 ('2015-02-09', 'namew'),

 ('2015-02-12', 'namen'),

 ('2015-02-13', 'named')]

>>> from operator import itemgetter

>>> longest_subsequence(dates, 'weak', key=itemgetter(0))

[('2015-02-03', 'name1'),

 ('2015-02-04', 'nameg'),

 ('2015-02-04', 'name5'),

 ('2015-02-05', 'nameh'),

 ('2015-02-07', 'name0'),

 ('2015-02-08', 'nameh'),

 ('2015-02-09', 'namew'),

 ('2015-02-12', 'namen'),

 ('2015-02-13', 'named')]

>>> indices = set(longest_subsequence(dates, key=itemgetter(0), index=True))

>>> [e for i,e in enumerate(dates) if i not in indices]

[('2015-02-04', 'nameg'),

 ('1929-03-12', 'name4'),

 ('2023-07-01', 'name7'),

 ('2015-02-15', 'namex'),

 ('1980-12-23', 'name2')]

该答案部分是由于“ 代码审查”中的问题所启发，另一部分是由询问“无序”值的问题所启发。