CODEWITHSUNDEEP
c#algorithm
Matt Crouch
Matt Crouch

Reputation: 1738

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.

Range array 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

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

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.

Thanks everyone for taking a stab at this.

Upvotes: 0

Views: 4045

Answers (3)

ratul_FIU
ratul_FIU

Reputation: 1

{ Linear time solution in java, no dynamic programming needed. The closest problem is:
Longest increasing subsequence which needs O(N^2) DP solution.

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;
}

Upvotes: 0

Stephan202
Stephan202

Reputation: 61469

A 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)

Upvotes: 1

Antti Huima
Antti Huima

Reputation: 25522

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.

Upvotes: 3

Related Questions