最有效的方法，以找到最长的名单

Question

名单递增序列我做了一些信号分析，其中一部分是要找到最长子

我的字典如下所示：

sequenceDict = { 
    0: [168, 360, 470], 
    1: [279, 361, 471, 633, 729, 817], 
    2: [32, 168, 170, 350, 634, 730, 818], 
    3: [33, 155, 171, 363, 635, 731, 765, 819], 
    4: [352, 364, 732, 766, 822], 
    5: [157, 173, 353, 577, 637, 733, 823, 969], 
    6: [158, 174, 578, 638, 706, 734, 824], 
    7: [159, 175, 579, 707, 735], 
    8: [160, 464, 640, 708, 826], 
    9: [173, 709, 757, 827], 
    10: [174, 540, 642, 666, 710], 
    11: [253, 667, 711], 
    12: [254, 304, 668], 
    13: [181, 255, 831], 
    14: [256, 340, 646, 832], 
    16: [184, 416], 
    17: [417], 
    18: [418], 
    19: [875], 
    20: [876], 
    23: [217], 
    24: [168, 218, 880], 
    25: [219, 765, 881], 
    26: [220, 766], 
    27: [221], 
    28: [768], 
    29: [3, 769], 
    30: [344, 476, 706]} 

这些基本上都是另一个数组的排序索引，我希望找到最长的递增序列（就像一个longest increasing subsequence），通过从每个键中只依次选择一个数字（键2在键1之后等），例如，来自键0和1的 ，[360,361]是一个序列，并且[470,471]是另一个。 我呼吁这些递增过程，因为这些数字应严格增加1

我看过的东西像patience sorting等，但由于这个问题略有不同，也有序列的一棵树，在那里任何已知的python实现或者其他有效的方法来执行此操作，除了从此dict生成所有可能的序列，然后运行耐心排序？

Answer 1

相较于@ 6502的解决方案，这其中不仅保持最佳的解决方案与价值735结束了7元素序列，但还跟踪每增加一个子序列，如果这更有帮助。

这个想法与滑动窗口方法类似。你开始从第一个列表，更新currentHotItems和globalHotItems字典，然后看第二个列表，再次更新词典等

# 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] 

globalHotItems是包含结果的字典。键是（value，startIndex），值是长度。

例如，最后4个项目中globalHotItems：

print sorted(globalHotItems.items(), key=lambda x:x[1])[-4:] 

是：

[((157, 5), 4), ((217, 23), 5), ((706, 6), 6), ((729, 1), 7)] 

这意味着最好的解决办法是长度7和在index=1列表开始作为729而最好第二种解决方案是长度为6，并且在index=6列表中起始为706等。

复杂度：

我认为复杂性应再次：O(input_size × average_number_of_sequences)

Answer 2

我只想实现一个“蛮力”解决方案......

1. 保持“当前序列”的列表，初始为空
2. 每个重点检查是否有任何当前的序列可延伸一步。增加序列更新时也是最好的解决方案。
3. 对没有用于扩展序列中任意数量开始长度的新序列1

Python提供set，其可以是合理的选择...这是一个示例实现：

best = None 
current_sequences = set() 
last_key = None 
for key in sorted(sequenceDict.keys()): 
    data = set(sequenceDict[key]) 
    new_sequences = set() 
    if last_key == key-1: 
     # no gap in key value, may be some sequence got extended 
     for val, count in current_sequences: 
      if val+1 in data: 
       # found a continuation, keep this sequence 
       new_sequences.add((val+1, count+1)) 
       data.remove(val+1) 
       if best is None or count+1 > best[0]: 
        # we've got a new champion 
        best = count+1, val+1, key 
    # add new sequences starting here 
    for v in data: 
     new_sequences.add((v, 1)) 
     if best is None: 
      best = 1, v, key 
    current_sequences = new_sequences 
    last_key = key 

一个棘手的部分是，如果在密钥中存在间隙，那么您无法扩展序列，这就是last_key的用途。

复杂性应该是O(input_size × average_number_of_sequences)。我只是一个直觉，但我的猜测是，你不能低于这个水平。我被使用value - key将恒定值与每个序列相关联的想法所诱惑...然而，这不会检测到“间隙”（即，密钥2中的密钥1中的值100和密钥3中的值102，而密钥2中的101没有101 ）。

随着问题输入的解决方案是(7, 735, 7)意味着在关键的7