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)