最长的连续子序列算法 [英] Longest contiguous subsequence algorithm

问题描述

我有范围的对象与属性偏移和持续，如下所示的阵列。假设它会通过偏移按升序进行排序。

I have an array of "Range" objects with properties "Offset" and "Length", as shown below. Assume that it'll be sorted by "Offset" ascending.

范围数组包含：

Offset        Length     Index
-------       -------    -------
100           10         0
110           2          1 
112           5          2
117           3          3
300           5          4
305           5          5 
400           5          6
405           10         7
415           2          8
417           4          9
421           7          10
428           1          11 
429           6          12  
500           4          13
504           9          14

在这种情况下的连续子序列将是：

The contiguous subsequences in this case would be:

Sequence #1 indices: 0, 1, 2, 3
Sequence #2 indices: 4, 5
Sequence #3 indices: 6, 7, 8, 9, 10, 11, 12  <-- (longest!!)
Sequence #4 indices: 13, 14

假设有只会有一个最长的序列。通过项迭代，我想创建为每个连续序列的新数组并返回最大数组，但似乎亚最佳。有没有更好的办法做到这一点？我实现在C＃2.0。该函数要么返回包含最长序列，或起始的元素和原始数组中结束最长序列的索引的阵列。

Assume that there will only be one longest sequence. Iterating through the items, i thought to create a new array for each contiguous sequence and return the biggest array, but that seem sub-optimal. Is there a better way to do this? I'm implementing in C# 2.0. The function should either return an array containing the elements of the longest subsequence, or the starting and ending indices of the longest subsequence in the original array.

感谢大家采取刺在此。

推荐答案

这个问题是不相关的连续子序列问题等，而是一个简单的问题，它可以在O（n）的时间来解决。在我看来，该弦重新$ P $的数组psented不重叠，所以有一个很简单的算法：把左手食指的第一行上，然后运行右手食指向下，只要你是一个连续序列中。当序列结束时，存储长度和起始位置。然后重复这一点。当你发现比previous记录更长的序列中，更新的起始位置。

This problem is not related to contiguous subsequence problem etc. but is a simple problem which can be solved in O(n) time. It seems to me that the "strings" represented by the array are not overlapping, so there is a very simple algorithm: put left index finger on the first row, and then run the right index finger downwards as long as you are within a contiguous sequence. When the sequence ends, store the length and the starting location. Then repeat this. Whenever you find a longer sequence than the previous record, you update the starting location.

这篇关于最长的连续子序列算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！