給定輸入序列，找到最長（不一定連續）非遞減子序列的最佳方法是什么。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會很好，但是一切都很好。
3 回答
慕俠2389804
TA貢獻1719條經驗 獲得超6個贊
這是一個相當通用的解決方案：
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')]
該答案部分是由于“ 代碼審查”中的問題所啟發，另一部分是由詢問“無序”值的問題所啟發。
添加回答
舉報
0/150
提交
取消