找到最长的非重叠序列的算法

使用给定的顺序（通过start元素）遍历元组列表，同时使用哈希图跟踪以某个索引 结尾 的最长连续序列的长度。

伪代码，跳过诸如在哈希图中找不到的项目之类的详细信息（假设未找到，则返回0）：

int bestEnd = 0;hashmap<int,int> seq // seq[key] = length of the longest sequence ending on key-1, or 0 if not foundforeach (tuple in orderedTuples) {    int seqLength = seq[tuple.start] + tuple.length    int tupleEnd = tuple.start+tuple.length;    seq[tupleEnd] = max(seq[tupleEnd], seqLength)    if (seqLength > seq[bestEnd]) bestEnd = tupleEnd}return new tuple(bestEnd-seq[bestEnd], seq[bestEnd])

这是一个O（N）算法。

如果您需要实际的元组组成此序列，则还需要保留一个由结束索引散列的元组链接列表，并在为此端点更新最大长度时进行更新。

更新：我对python的了解非常有限，但是基于您粘贴的python代码，我创建了以下代码，该代码返回实际序列而不是长度：

def get_longest(arr):    bestEnd = 0;    seqLengths = dict() #seqLengths[key] = length of the longest sequence ending on key-1, or 0 if not found    seqTuples = dict() #seqTuples[key] = the last tuple used in this longest sequence    for t in arr:        seqLength = seqLengths.get(t[0],0) + t[1]        tupleEnd = t[0] + t[1]        if (seqLength > seqLengths.get(tupleEnd,0)): seqLengths[tupleEnd] = seqLength seqTuples[tupleEnd] = t if seqLength > seqLengths.get(bestEnd,0):     bestEnd = tupleEnd    longestSeq = []    while (bestEnd in seqTuples):        longestSeq.append(seqTuples[bestEnd])        bestEnd -= seqTuples[bestEnd][1]    longestSeq.reverse()    return longestSeqif __name__ == "__main__":    a = [(0,3),(1,4),(1,1),(1,8),(5,2),(5,5),(5,6),(10,2)]    print(get_longest(a))