<p><strong>与@6502的解相比,这个解不仅保持了最佳解,而且还跟踪了每一个递增的子序列,如果这更有帮助的话。</strong></p>
<p>这个想法类似于滑动窗口方法。从第一个列表开始,更新<code>currentHotItems</code>和{<cd2>}字典,然后查看第二个列表并再次更新字典,等等</p>
<pre><code># fill missing indexes in the dictionary:
for i in range(min(sequenceDict), max(sequenceDict)):
if i not in sequenceDict:
sequenceDict[i] = []
# get only lists, ordered:
sortedItems = map(lambda x:x[1], sorted(sequenceDict.items(), key=lambda x:x[0]))
globalHotItems = {} # (value, startIndex): length
currentHotItems = {} # value: length
for i in range(len(sortedItems)):
updatedHotItems = {} # updated value: length
for item in sortedItems[i]:
if (item - 1) in currentHotItems:
updatedHotItems[item] = currentHotItems[item-1] + 1
else:
updatedHotItems[item] = 1
deadSet = set(currentHotItems.keys()) - \
set(updatedHotItems.keys() + [key - 1 for key in updatedHotItems.keys()])
for item in deadSet:
globalHotItems[ (item-currentHotItems[item]+1, i-currentHotItems[item]) ] = currentHotItems[item]
currentHotItems = updatedHotItems
print sorted(globalHotItems.items(), key=lambda x:x[1])[-1]
</code></pre>
<p><code>globalHotItems</code>是包含结果的字典。键是(value,startIndex),value是长度。在</p>
<p>例如,<code>globalHotItems</code>中的最后4项:</p>
^{pr2}$
<p>是:</p>
<pre><code>[((157, 5), 4), ((217, 23), 5), ((706, 6), 6), ((729, 1), 7)]
</code></pre>
<p>这意味着最好的解决方案是长度7,从<code>index=1</code>列表中开始为729。最好的第二个解是长度6,从<code>index=6</code>列表开始,如706,等等</p>
<p><strong>复杂性:</strong></p>
<p>我认为复杂性应该是:<code>O(input_size × average_number_of_sequences)</code></p>