最长的递增子序列

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

这是一个相当通用的解决方案：O(n log n)及时运行处理增加，减少，减少和增加的子序列，与任何序列对象，包括工程list，numpy.array，str多，通过key参数（类似于内置sorted函数中的参数）支持对象列表和自定义比较方法，可以返回子序列的元素或其索引。编码：from bisect import bisect_left, bisect_rightfrom functools import cmp_to_keydef longest_subsequence(seq, mode='strictly', order='increasing',&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; key=None, index=False):&nbsp; bisect = bisect_left if mode.startswith('strict') else bisect_right&nbsp; # compute keys for comparison just once&nbsp; rank = seq if key is None else map(key, seq)&nbsp; if order == 'decreasing':&nbsp; &nbsp; rank = map(cmp_to_key(lambda x,y: 1 if x<y else 0 if x==y else -1), rank)&nbsp; rank = list(rank)&nbsp; if not rank: return []&nbsp; lastoflength = [0] # end position of subsequence with given length&nbsp; predecessor = [None] # penultimate element of l.i.s. ending at given position&nbsp; for i in range(1, len(seq)):&nbsp; &nbsp; # seq[i] can extend a subsequence that ends with a lesser (or equal) element&nbsp; &nbsp; j = bisect([rank[k] for k in lastoflength], rank[i])&nbsp; &nbsp; # update existing subsequence of length j or extend the longest&nbsp; &nbsp; try: lastoflength[j] = i&nbsp; &nbsp; except: lastoflength.append(i)&nbsp; &nbsp; # remember element before seq[i] in the subsequence&nbsp; &nbsp; predecessor.append(lastoflength[j-1] if j > 0 else None)&nbsp; # trace indices [p^n(i), ..., p(p(i)), p(i), i], where n=len(lastoflength)-1&nbsp; def trace(i):&nbsp; &nbsp; if i is not None:&nbsp; &nbsp; &nbsp; yield from trace(predecessor[i])&nbsp; &nbsp; &nbsp; yield i&nbsp; indices = trace(lastoflength[-1])&nbsp; return list(indices) if index else [seq[i] for i in indices]我为上面没有粘贴的函数编写了一个文档字符串，以展示代码："""Return the longest increasing subsequence of `seq`.Parameters----------seq : sequence object&nbsp; Can be any sequence, like `str`, `list`, `numpy.array`.mode : {'strict', 'strictly', 'weak', 'weakly'}, optional&nbsp; If set to 'strict', the subsequence will contain unique elements.&nbsp; Using 'weak' an element can be repeated many times.&nbsp; Modes ending in -ly serve as a convenience to use with `order` parameter,&nbsp; because `longest_sequence(seq, 'weakly', 'increasing')` reads better.&nbsp; The default is 'strict'.order : {'increasing', 'decreasing'}, optional&nbsp; By default return the longest increasing subsequence, but it is possible&nbsp; to return the longest decreasing sequence as well.key : function, optional&nbsp; Specifies a function of one argument that is used to extract a comparison&nbsp; key from each list element (e.g., `str.lower`, `lambda x: x[0]`).&nbsp; The default value is `None` (compare the elements directly).index : bool, optional&nbsp; If set to `True`, return the indices of the subsequence, otherwise return&nbsp; the elements. Default is `False`.Returns-------elements : list, optional&nbsp; A `list` of elements of the longest subsequence.&nbsp; Returned by default and when `index` is set to `False`.indices : list, optional&nbsp; A `list` of indices pointing to elements in the longest subsequence.&nbsp; 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"&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;" (not necessarily continuous) non-decreasing subsequence.")>>> ''.join(longest_subsequence(txt))' ,abdegilnorsu'>>> ''.join(longest_subsequence(txt, 'weak'))'&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ceilnnnnrsssu'>>> ''.join(longest_subsequence(txt, 'weakly', 'decreasing'))'vuutttttttssronnnnngeee.'>>> dates = [...&nbsp; &nbsp;('2015-02-03', 'name1'),...&nbsp; &nbsp;('2015-02-04', 'nameg'),...&nbsp; &nbsp;('2015-02-04', 'name5'),...&nbsp; &nbsp;('2015-02-05', 'nameh'),...&nbsp; &nbsp;('1929-03-12', 'name4'),...&nbsp; &nbsp;('2023-07-01', 'name7'),...&nbsp; &nbsp;('2015-02-07', 'name0'),...&nbsp; &nbsp;('2015-02-08', 'nameh'),...&nbsp; &nbsp;('2015-02-15', 'namex'),...&nbsp; &nbsp;('2015-02-09', 'namew'),...&nbsp; &nbsp;('1980-12-23', 'name2'),...&nbsp; &nbsp;('2015-02-12', 'namen'),...&nbsp; &nbsp;('2015-02-13', 'named'),... ]>>> longest_subsequence(dates, 'weak')[('2015-02-03', 'name1'),&nbsp;('2015-02-04', 'name5'),&nbsp;('2015-02-05', 'nameh'),&nbsp;('2015-02-07', 'name0'),&nbsp;('2015-02-08', 'nameh'),&nbsp;('2015-02-09', 'namew'),&nbsp;('2015-02-12', 'namen'),&nbsp;('2015-02-13', 'named')]>>> from operator import itemgetter>>> longest_subsequence(dates, 'weak', key=itemgetter(0))[('2015-02-03', 'name1'),&nbsp;('2015-02-04', 'nameg'),&nbsp;('2015-02-04', 'name5'),&nbsp;('2015-02-05', 'nameh'),&nbsp;('2015-02-07', 'name0'),&nbsp;('2015-02-08', 'nameh'),&nbsp;('2015-02-09', 'namew'),&nbsp;('2015-02-12', 'namen'),&nbsp;('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'),&nbsp;('1929-03-12', 'name4'),&nbsp;('2023-07-01', 'name7'),&nbsp;('2015-02-15', 'namex'),&nbsp;('1980-12-23', 'name2')]该答案部分是由于“ 代码审查”中的问题所启发，另一部分是由询问“无序”值的问题所启发。