Longest increasing sub-sequence
The longest increasing sub-sequence problem is to find a sub-sequence of a given sequence in which the sub-sequence's elements are in sorted order, lowest to highest, and in which the sub-sequence is as long as possible. The longest increasing sub-sequence is solvable in O(nlogn) time complexity and O(n) space complexity in worst scenario.
In the first 16 terms of the binary Van der Corput sequence
- 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15
a longest increasing sub-sequence is
- 0, 2, 6, 9, 11, 15.
This sub-sequence has length six; the input sequence has no seven-member increasing sub-sequences. The longest increasing sub-sequence in this example is not unique: for instance,
- 0, 4, 6, 9, 11, 15 or 0, 4, 6, 9, 13, 15
are other increasing sub-sequence of equal length in the same input sequence.
See the figure below as to how it is done.
We have similar approach in which we check the following condition before inserting an element in a sorted array
Case 1
If next element is already greater than the last element of the sorted array. Add it in the last of the sorted array.
Case 2
If next element is less than the first element of the sorted array. then replace it with first element in the sorted array with this element.
Case 3
If A[i] is in between, we will find an index in list such that for every 0<=j<=n in the list, A[i]>list(j)
To find the index of an element in an sorted array with least index greater than A[i], we will use modified Binary Search.
public class LIS {
public static void main(String[] args) throws FileNotFoundException {
int a[] = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 13, 3, 11, 7, 15 };
System.out.println(lis2(a));
System.out.println(lis3(a));
}
/**
* Arraylist version with nlogn time and <=n space, will take less space
* than array version. Steps 1 Create an array of same size. 2 Check the
* next element from the input 3. if it is greater than the last element in
* our array then add it into the end of the list. 4. if it is less than the
* first element in our array then replace the first element 5. if it can be
* inserted into our list then find out where it can be inserted and insert
* it by replacement.
*
* @param a
* @return
*/
private static int lis2(int[] a) {
List<Integer> lis = new ArrayList<>();
lis.add(a[0]);
for (int i = 1; i < a.length; i++)
if (a[i] > lis.get(lis.size() - 1))
lis.add(a[i]);
else if (a[i] < lis.get(0))
lis.set(0, a[i]);
else
lis.set(binarySearch(lis, a[i]), a[i]);
System.out.println(lis);
return lis.size();
}
/**
* Array version with nlogn time complexity and n space.
*
* @param a
* @return
*/
private static int lis3(int[] a) {
int[] lis = new int[a.length];
int lastIndex = 0;
lis[lastIndex] = a[0];
for (int i = 1; i < a.length; i++)
if (a[i] > lis[lastIndex])
lis[++lastIndex] = a[i];
else if (a[i] < lis[0])
lis[0] = a[i];
else
lis[binarySearch(lis, 0, lastIndex, a[i])] = a[i];
return lastIndex + 1;
}
/**
* O(n^2) log time, very slow performance.
*
* @param arr
* @return
*/
private static int lis(int[] arr) {
int max = -1;
int[] lis = new int[arr.length];
lis[0] = 1;
for (int i = 1; i < arr.length; i++)
for (int j = 0; j < i; j++)
if (arr[i] > arr[j] && lis[i] < lis[j] + 1) {
lis[i] = lis[j] + 1;
max = Math.max(max, lis[i]);
}
return max;
}
/**
* least index greater than n
*
* @param a
* @param n
* @param low
* @param high
* @return
*/
private static int binarySearch(int[] a, int low, int high, int key) {
while (low <= high) {
int mid = (low + high) >>> 1;
int midVal = a[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return low; // key not found.
}
private static int binarySearch(List<Integer> a, int key) {
int low = 0;
int high = a.size() - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
int midVal = a.get(mid);
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return low; // key not found.
}
}
No comments:
Post a Comment