使用给定的顺序（通过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))
