Longest Increasing Subsequence (LIS):
Problem statement:
Our aim here is to find out longest increasing
subsequence from the given sequence/array of integers. Note that the increasing
subsequence need not to be continuous.
Let’s trace below scenario,
If the original sequence is {15, 27, 14, 38, 26, 55, 46, 65,
85} then, possible increasing subsequence would be,
Original Sequence. (Input)
|
Increasing Subsequence. (output)
|
Length
|
|
1.
|
{15, 27, 14, 38, 26, 55, 46, 65,
85}
|
{15, 27, 38, 55, 65, 85}
|
6.
|
2.
|
{15, 27, 14, 38, 26, 55, 46, 65, 85}
|
{14, 26, 46, 65, 85}
|
5.
|
Approach:
We can solve this problem using dynamic programming. I’m
going to create two arrays. One to store reference of previous element(arr1),
another will store temporary sequence of increasing elements(arr2).
Case-I.
Append current element to the subsequence only if the
previous element is smaller than the current one.
(Note: Current element is
the element at the ith position while running the loop over an input
sequence.)
Current Element
|
Subsequence
|
Final Subsequence
|
Length
|
{4}
|
{1, 2, 3}
|
{1, 2, 3, 4}
|
4
|
Here, Element 4 will hold the index of 3, 3 will index of
2 and so on and so forth as shown below,
1
|
-1(default)
|
2
|
Index=0
|
3
|
Index=1
|
4
|
Index=2
|
Case-II.
Find the celling in case, current element is smaller than
the last element and greater than the first element. And just replace the ceiling
with the current element.
(Note: Current element is
the element at the ith position while running the loop over an input
sequence.)
Current Element
|
Subsequence
|
Final Subsequence
|
Length
|
{3}, assumed index=7
|
{1, 5, 7}
|
{1, 3, 7}
|
3
|
Here, Element 7 will hold the index of 3(which is 7), 3
will index of 1 and so on and so forth as shown below,
1
|
-1(default)
|
3
|
Index=0
|
7
|
Index=7
|
Case-III.
If the current element is smaller than the first element
of the subsequence. Then replace the first element with the current element
(Note: Current element is
the element at the ith position while running the loop over an input
sequence.)
Current Element
|
Subsequence
|
Final Subsequence
|
Length
|
{0}, assumed index=6
|
{1, 2, 3}
|
{0, 2, 3}
|
3
|
Here, Element 3 will hold the index of 2, 2 will index of
0(which is 6) and so on and so forth as shown below,
0
|
-1(default)
|
2
|
Index=6
|
3
|
Index=1
|
If I run through the given input sequence using above
logic then, I’ll end up with below mentioned array which is pointing to the
index of its previous element.
Loop-i
|
Current
Element
|
Arr2
|
Arr1(Initialized with -1)
|
Length
|
Loop-0
|
15
|
{15}
|
{-1, -1, -1, -1, -1, -1, -1, -1,
-1}
|
1
|
Loop-1
|
27
|
{15, 27}
|
{-1, 0, -1, -1, -1, -1, -1, -1, -1}
|
2
|
Loop-2
|
14
|
{14, 27}
|
{-1, 0, -1, -1, -1, -1, -1, -1,
-1}
|
2
|
Loop-3
|
38
|
{14, 27, 38)
|
{-1, 0, -1, 1, -1, -1, -1, -1, -1}
|
3
|
Loop-4
|
26
|
{14, 26, 38)
|
{-1, 0, -1, 1, 2, -1, -1, -1, -1}
|
3
|
Loop-5
|
55
|
{14, 26, 38, 55)
|
{-1, 0, -1, 1, 2, 3, -1, -1, -1}
|
4
|
Loop-6
|
46
|
(14, 26, 38, 46}
|
{-1, 0, -1, 1, 2, 3, 3, -1, -1}
|
4
|
Loop-7
|
65
|
{14, 26, 38, 46, 65}
|
{-1, 0, -1, 1, 2, 3, 3, 6, 7}
|
5
|
Loop-8
|
85
|
{14, 26, 38, 46, 65, 85}
|
{-1, 0, -1, 1, 2, 3, 3, 6, 7}
|
6
|
So, my Longest Increasing Subsequence would be,
- To find ceiling from the sorted array, we are using binary search (log(n)).
- Also, we are iterating through an entire sequence of n elements.
So in worst-case Time complexity of this algorithm would be O(n logn).
Code:
package com.mayank4java;
public class LISAlgorithm {
private Data tempArray[];
private int sequencePointerArray[];
private int lengthOfSequence = 0;
public LISAlgorithm() {}
private static class Data {
int index;
int value;
}
public int findCeiling(Data array[], int searchElement, int max) {
int min = 0;
int avg = 0;
if (searchElement < array[0].value)
return 0;
for (int j = 0; j < max; j++) {
if (max >= min)
avg = (max + min) / 2;
if (searchElement == array[min].value)
return array[min].index;
else if (searchElement == array[max].value)
return array[max].index;
else if (searchElement == array[avg].value)
return array[avg].index;
else if (max - min == 1)
return max;
else if (searchElement > array[avg].value)
min = avg;
else if (searchElement < array[avg].value)
max = avg;
}
return avg;
}
public void doLIS(int[] intSequence) {
sequencePointerArray = new int[intSequence.length];
tempArray = new Data[intSequence.length];
sequencePointerArray[0] = -1;
Data data = new Data();
data.value = intSequence[0];
data.index = 0;
tempArray[0] = data;
for (int i = 1; i < intSequence.length; i++) {
sequencePointerArray[i] = -1;// initializing elements to -1.
if (intSequence[i] > tempArray[lengthOfSequence].value) {
++lengthOfSequence;
data = new Data();
data.value = intSequence[i];
data.index = i;
tempArray[lengthOfSequence] = data;
sequencePointerArray[i] = tempArray[lengthOfSequence - 1].index;
} else {
int index = findCeiling(tempArray, intSequence[i], lengthOfSequence);
data = new Data();
data.value = intSequence[i];
data.index = i;
tempArray[index] = data;
if (index != 0)
sequencePointerArray[i] = tempArray[index - 1].index;
}
}
int pointer = tempArray[lengthOfSequence].index;
for (int i = 0; i < sequencePointerArray.length; i++) {
System.out.println(intSequence[pointer]);
pointer = sequencePointerArray[pointer];
if (pointer == -1)
break;
}
}
public static void main(String[] args) {
int sequence[] = { -11, -5, -10, 0, 12, 13, 1, 2, 3 };
/*int sequence[] = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 };*/
/*int sequence[] = {0, 12,13,1,2,3};*/
/*int sequence[] = {0,7,8,1};*/
LISAlgorithm lis = new LISAlgorithm();
lis.doLIS(sequence);
}
}
That is it!😃
Hope this post helped you.Also don't forget to share and leave your comments below.
Comments
Post a Comment