Non overlapping maximum subsequence

Given n sequences, and starting and stopping point of every sequence with its score. For eg.
no of sequences = 5
start stop score
0 4 4
3 10 11
6 8 8
7 15 10
11 15 4

All scores are positive. You have to find the maximum subset of non overlapping sequences having maximum total sum of scores.

In above example, maximum total of non overlapping sub-sequence is 16. [{0,4,4},{6,8,8},11,15,4}]

Solution : This problem is very much similar to LIS sequence. We have to find longest sequence in which start point of later sequence is greater than stop point of previous sequences.Here we are using an extra array prev to be able to find the actual sequence.

#include<iostream>
#include<malloc.h>
using namespace std;
 
// Structure for a seq
struct seq
{
  int start;
  int stop;
  int score;
};
 
int maxSequenceSum( struct seq arr[], int n)
{
   int i, j,bestEnd, maxLength = 1,sum = 0;
   int *L = (int*) malloc ( sizeof( int ) * n );
   int *prev = (int*) malloc ( sizeof( int ) * n );
   
   L[0] = 1;
   prev[0]=-1;
 
	for ( i = 1; i < n; i++ )
	{
		L[i]=1;
		prev[i]=-1;   
		for ( j = 0; j < i; j++ )
		{
			if ( arr[i].start > arr[j].stop && L[i] < L[j] + 1)
			{ 
				L[i] = L[j] + 1;
				prev[i]=j;
			}
		}		
		if ( maxLength < L[i] )
		{
			maxLength = L[i];
			bestEnd = i;
		}
	}

	for(i = bestEnd;i>=0;)
	{       
                sum+=arr[i].score;
		i = prev[i];
	}
 
   /* Free memory to avoid memory leak */
   free( L );
 
   return sum;
}

int main()
{
    struct seq arr[] = {{0,4,4},{3,10,11},{6,8,8},{7,15,10},{11,15,4}};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    cout<<maxSequenceSum( arr, n );
    return 0;
}

Time Complexity : O(N^2)

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation