The longest continuous subsequence algorithm

Question

I have an array of Range objects with the Offset and Length properties, as shown below. Suppose it is sorted in ascending order by "Offset".

The array range contains:

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 

Adjacent subsequences in this case will 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 

Suppose there will be only one long sequence. Iterating over the elements, I was thinking of creating a new array for each continuous sequence and returning the largest array, but this seems suboptimal. Is there a better way to do this? I am implementing in C # 2.0. The function must either return an array containing the elements of the longest subsequence, or the start and end indices of the longest subsequence in the original array.

Thank you all for striking.

Answer 1

This problem is not related to the sequential problem of subsequence, etc., but is a simple problem that can be solved in O (n) time. It seems to me that the "lines" represented by the array do not overlap, so there is a very simple algorithm: put the left index finger on the first line, and then run the right index finger down while you are in the adjacent sequence. When the sequence ends, save the length and initial location. Then repeat this. Whenever you find a longer sequence than the previous record, you update the starting position.

Answer 2

Simple linear algorithm (Python, I'm sure the code can be improved):

 # Your array arr = [ (100, 10), (110, 2), (112, 5), (117, 3), (300, 5), (305, 5), (400, 5), (405, 10), (415, 2), (417, 4), (421, 7), (428, 1), (429, 6), (500, 4), (504, 9) ] # Where does each element end? ends = map(sum, arr) s, e = 0, 0 # start and end of longest contiguous subseq cur = 0 # length of current contiguous subseq for j, i in enumerate(range(1, len(arr))): # See if current element is contiguous with the previous one if (arr[i][0] == ends[j]): cur += 1 elif cur > 0: # If not, we may have found the end of a (currently) longest subseq if cur > (e - s): e = j s = e - cur cur = 0 # reset subseq length # The longest contiguous subseq may be at the end of the array if cur > (e - s): e = j + 1 s = e - cur # print the start and end index of the longest contiguous subseq print(s, e) 

Answer 3

{Linear time solution in java, no dynamic programming required. Closest problem: • The longest increasing subsequence that needs to be resolved O(N^2) DP.

 int LongestContiguousIncreasingSubsequence(int[] a) { int maxL = 1,currentL=1; int n=a.length; for ( int i = 0; i < n-1; i++ ) { if(a[i+1]>a[i]) currentL++; else { if (currentL>maxL) maxL=currentL; currentL=1; } } return maxL; }