Problem Statement:
Suppose you have a given a integer sequence a[1..n]. You have to find the longest increasing sub sequence i.e. the sub sequence should be in increasing order with largest length possible in the given sequence.
Let suppose you have following sub sequence:
Longest increasing sub sequence is : 0, 2, 3, 4, 9, 12, 15.
is there any other longest or same length sub sequence is there?
Yes : 0, 2, 3, 4, 8, 12, 15
So both have the same length 7. Make sure no other sub sequence should have length greater than 7.
Just try ? If you able to find please add comment in the post we will discuss that.
So our main problem is how to solve this problem programatically? We will again discuss the various approach and then the one with Dynamic programming.
Solution Approach:
Brute Force Approach:
In brute force approach we will calculate all the possible sub sequence and then check for the longest sub sequence. So for calculating all the sub sequence is tedious task and take O(2n) complexity.If three elements are there like
0
2
7
0, 2
0, 7
2, 7
0, 2, 7
So we have all the possible combination and longest is 0, 2, 7. So it is not a optimum solution.
We will not go with the solution.
Dynamic Approach:
We know that to solve any problem with dynamic approach it must have two attributes:
Optimal Substructure:
The solution is known has optimal sub structure if optimal solution can be construct from the optimal solutions of sub problem.
Can we do that in this situation ?
In above scenario what if i know that the longest sub sequence for all the indexes upto 5. Can i use that for calculating the sub sequence for index 6 ?
Yes the sub sequence of index 6 can be
longSubsequence (6) = {
max(longSubsequnce(j) + 1) where j:1...5 and if a[6] > a[j],
1 if no j found such that all a[j] is greater than a[6].
}
So longest sub sequence of 6 can be calculated if we know the longest sub sequence of 5. So solution has optimum Sub structure.
Overlapping Subproblem(Recursion):
For Solving the maxSubsequence of 6 we need to solve the longestsubsequence of 5, 4, 3, 2 and1. So the problem has recursion possibly.
Solution:
We will start with the longest sub sequence for index 0 and go upto array length.
ls[0] = 1 //Only one element can be in sub sequence for length 1 array.
ls[1] = 2 // (0, 2) as a[1] is greater than a[0] So we can add it.
ls[2] = 1+ max(ls[0],ls[1]) as 7 is greater than both 0 and 2.
ls[2] = 1+max(1, 2)
= 3
ls[3] = 1+max(ls[0], ls[1]) as a[3] < a[2] So we cannot consider that in the formula.
ls[3] = 1+max(1, 2)
= 3
ls[4] = 1+max(ls[0], ls[1], ls[3]) as a[4] is less than a[2] so we cannot consider this
ls[4] = 1+max(1, 2, 3)
= 4
ls[5] = 1+max(ls[0], ls[1], ls[2], ls[3], ls[4]) as 9 is greater than all the previous element.
= 1+ max(1, 2, 3, 3, 4)
= 5
ls[6] = 1+max(ls[0], ls[1], ls[2], ls[3], ls[4]) as 8 is less than 9 the previous element.
= 1+ max(1, 2, 3, 3, 4)
= 5
ls[7] = 1+max(ls[0], ls[1], ls[2], ls[3], ls[4], ls[5], ls[6]) as 12 is greater than all the previous element.
= 1+ max(1, 2, 3, 3, 4, 5, 5)
= 6 (0, 2, 3, 4, 9, 12) or (0, 2, 3, 4, 8, 12)
ls[8] = 1 as a[8] is less than all the previous element.
ls[9] = 1+max(ls[0], ls[1], ls[2], ls[3], ls[4], ls[5], ls[6], ls[7], ls[8]) as 15 is greater than all the previous element.
= 1+ max(1, 2, 3, 3, 4, 5, 5, 6, 1)
= 7 (0, 2, 3, 4, 9, 12, 15) or (0, 2, 3, 4, 8, 12, 15)
So we have solution with the above approach. Can we phrase the solution in one formula:
ls[i] = 1+max(ls[j]) where j:0...i if a[i] > a[j]
or
1 if no such j found.
So I have implemented the solution using C. Following is the solution:
I am using a heap to store longest sub sequence for each index. Like for zero index the longest sub sequence only have one length and first element. So other we are calculating based on that above formula.
Following is heap structure:
//Use as a heap for store the longest sequence for index
typedef struct lsIncreasingSequence_struct{
int longesubSequence[10];
int longesubequenceLength;
}lsIncreasingSequence;
Calculating the longest sub sequence following is the code:
//return the longest sequence
lsIncreasingSequence longIncSubsequence(int sequence[], int seqL){
lsIncreasingSequence lsubsequences[seqL+1]; //Store the longest sequence for each index
int finalsubsequenceLength = 0; //Store the longest sequence length
int finalSubSequenceIndex = -1; //Store the longest sequence index
lsubsequences[0].longesubSequence[0] = sequence[0]; //First sequence have only first element
lsubsequences[0].longesubequenceLength = 1; //First sequence have only first element so count is 1
//Loop Start from second element and count longest sequence for each index
for (int i=1; i<seqL; i++) {
//Loop check for all the possible sub sequence and check if length is largest
for(int j=0; j <i ; j++){
if(sequence[i] > sequence[j]){
finalsubsequenceLength = lsubsequences[j].longesubequenceLength + 1;
if(finalsubsequenceLength > lsubsequences[i].longesubequenceLength){
lsubsequences[i].longesubequenceLength = finalsubsequenceLength;
finalSubSequenceIndex = j; //Store the largest increasing sub sequence for index i
}
}
}
//loop copy all the elements of longest sub sequence of i to index i of heap
if(finalSubSequenceIndex != -1){
int k = 0;
for(; k < lsubsequences[i].longesubequenceLength-1; k++){
lsubsequences[i].longesubSequence[k] = lsubsequences[finalSubSequenceIndex].longesubSequence[k];
}
lsubsequences[i].longesubSequence[k] = sequence[i];
}
finalSubSequenceIndex = -1;
}
//loop calculate longest increasing sub sequence from all the indexs in a heap
finalsubsequenceLength = 0;
for (int k=0; k<seqL; k++) {
if(lsubsequences[k].longesubequenceLength > finalsubsequenceLength){
finalsubsequenceLength = lsubsequences[k].longesubequenceLength;
finalSubSequenceIndex = k;
}
}
//return the longest sub sequence heap element
return lsubsequences[finalSubSequenceIndex];
}
So the above method return the longest sub sequence.
You can download the running code from the link.
Please provide your suggestion.
No comments:
Post a Comment