The Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.
We are going to implement this algorithm in 4 different ways.
1. Using recursive method.
2. Optimized recursive method.
3. Dynamic programming.
4 Dynamic programming with binary search.
Lets start with the algorithm.
1. Using recursive method.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
package com.omt.learn.geekforgeek.dynamic; public class LIS { private static long startTime = 0; private static long MAX_LIS = 0; public static void main(String args[]) { setStartTime(); int a[] = {3, 10, 2, 1, 20}; MAX_LIS = 0; lis(a, 0); System.out.println(MAX_LIS); int b[] = {3, 2}; MAX_LIS = 0; lis(b, 0); System.out.println(MAX_LIS); int c[] = {50, 3, 10, 7, 40, 80}; MAX_LIS = 0; lis(c, 0); System.out.println(MAX_LIS); int d[] = {10, 22, 9, 33, 21, 50, 41, 60, 80}; MAX_LIS = 0; lis(d, 0); System.out.println(MAX_LIS); int e[] = {0, 8, 4, 12, 2, 10}; MAX_LIS = 0; lis(e, 0); System.out.println(MAX_LIS); int f[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}; MAX_LIS = 0; lis(f, 0); System.out.println(MAX_LIS); calculateEndTime(); } public static int lis(int a[], int start) { int end = a.length - 1; if (start >= end) { return 1; } int maxLIS = 1; for (int index = start + 1; index <= end; index++) { //Check what we have for next element. Calculate LIS for next element. int tempLIS = lis(a, index); //For input {50, 3, 10, 7, 40, 80} //Take start element and compare with all next selections. if (a[start] < a[index]) { tempLIS++; //Increase If start is less than neighbor //Calculation of current element maxLIS for current index. This if inside above if {0, 8, 4, 12, 2, 10} if (tempLIS > maxLIS) {//If tempLIS is greater than MaxLis maxLIS = tempLIS; } } } MAX_LIS = MAX_LIS < maxLIS ? maxLIS : MAX_LIS; return maxLIS; } private static void setStartTime() { startTime = System.currentTimeMillis(); } private static void calculateEndTime() { System.out.println("Time in ms:" + (System.currentTimeMillis() - startTime)); } } |
2. Optimized recursive method.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 |
package com.omt.learn.geekforgeek.dynamic; import java.util.Map; import java.util.TreeMap; public class LIS2 { private static long startTime = 0; private static long MAX_LIS = 0; public static void main(String args[]) { setStartTime(); int a[] = {3, 10, 2, 1, 20}; MAX_LIS = 0; lis(a, 0, new TreeMap<>()); System.out.println(MAX_LIS); int b[] = {3, 2}; MAX_LIS = 0; lis(b, 0, new TreeMap<>()); System.out.println(MAX_LIS); int c[] = {50, 3, 10, 7, 40, 80}; MAX_LIS = 0; lis(c, 0, new TreeMap<>()); System.out.println(MAX_LIS); int d[] = {10, 22, 9, 33, 21, 50, 41, 60, 80}; MAX_LIS = 0; lis(d, 0, new TreeMap<>()); System.out.println(MAX_LIS); int e[] = {0, 8, 4, 12, 2, 10}; MAX_LIS = 0; lis(e, 0, new TreeMap<>()); System.out.println(MAX_LIS); int f[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}; MAX_LIS = 0; lis(f, 0, new TreeMap<>()); System.out.println(MAX_LIS); calculateEndTime(); } public static int lis(int a[], int start, Map<Integer, Integer> CALCULATED_RESULT) { int end = a.length - 1; if (start >= end) { return 1; } int maxLIS = 1; for (int index = start + 1; index <= end; index++) { //Check what we have for next element. Calculate LIS for next element. int tempLIS = 1; //This way we can avoid calling same method again and again, which is more safe to avoid stackoverflow exception. if (CALCULATED_RESULT.containsKey(index)) { tempLIS = CALCULATED_RESULT.get(index); } else { tempLIS = lis(a, index, CALCULATED_RESULT); //For input {50, 3, 10, 7, 40, 80} } //Take start element and compare with all next selections. if (a[start] < a[index]) { tempLIS++; //Increase If start is less than neighbor if (tempLIS > maxLIS) {//If tempLIS is greater than MaxLis maxLIS = tempLIS; } } } MAX_LIS = MAX_LIS < maxLIS ? maxLIS : MAX_LIS; CALCULATED_RESULT.put(start, maxLIS); return maxLIS; } private static void setStartTime() { startTime = System.currentTimeMillis(); } private static void calculateEndTime() { System.out.println("Time in ms:" + (System.currentTimeMillis() - startTime)); } } |
3. Dynamic programming.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
package com.omt.learn.geekforgeek.dynamic; import java.util.Map; import java.util.TreeMap; public class LIS3 { public static void main(String args[]) { int a[] = {3, 10, 2, 1, 20}; System.out.println(lis(a)); int b[] = {3, 2}; System.out.println(lis(b)); int c[] = {50, 3, 10, 7, 40, 80}; System.out.println(lis(c)); int d[] = {10, 22, 9, 33, 21, 50, 41, 60, 80}; System.out.println(lis(d)); int f[] = {0, 8, 4, 12, 2, 10}; System.out.println(lis(f)); int e[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}; System.out.println(lis(e)); } private static int lis(int a[]) { int maxLIS = 1; int end = a.length - 1; Map<Integer, Integer> CALCULATED_RESULT = new TreeMap<>(); CALCULATED_RESULT.put(end, 1); // Last element has 1 as LIS. //Here we are using bottom up technique, Starting from bottom we will calculate LIS for each element. for (int i = end - 1; i >= 0; i--) { CALCULATED_RESULT.put(i, 1);//Default LIS is 1 for (int j = end; j > i; j--) {//Start with last element and move one by one at top. if (a[i] < a[j] && CALCULATED_RESULT.get(i) < (CALCULATED_RESULT.get(j) + 1)) { CALCULATED_RESULT.put(i, CALCULATED_RESULT.get(j) + 1); if (maxLIS < CALCULATED_RESULT.get(i)) { maxLIS = CALCULATED_RESULT.get(i); } } } } return maxLIS; } } |
4 Dynamic programming with binary search.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 |
package com.omt.learn.geekforgeek.dynamic; import java.util.ArrayList; import java.util.List; public class LIS4 { public static void main(String... args) { int a[] = {3, 10, 2, 1, 20}; System.out.println(lis(a)); int b[] = {3, 2}; System.out.println(lis(b)); int c[] = {50, 3, 10, 7, 40, 80}; System.out.println(lis(c)); int d[] = {10, 22, 9, 33, 21, 50, 41, 60, 80}; System.out.println(lis(d)); int f[] = {0, 8, 4, 12, 2, 10}; System.out.println(lis(f)); int e[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}; System.out.println(lis(e)); } private static int lis(int a[]) { if (a.length == 0) { return 0; } else if (a.length == 1) { return 1; } List<Integer> lis = new ArrayList<>(); List<Integer> lastElement = new ArrayList<>(); lis.add(1); lastElement.add(a[0]); for (int index = 1; index < a.length; index++) { int element = a[index]; int position = findPosition(element, lastElement); if (position == lastElement.size()) { // This means element is biggest, Create new entry in lastElement lastElement.add(element); lis.add(1 + lis.get(position - 1)); } else { // Replace in between element with same position. lastElement.set(position, element); //Since we are replacing element at position, Here no need to set LIS, } //System.out.println("Lis :" + lis.toString()); //System.out.println("Element :" + lastElement.toString()); } return lis.get(lis.size() - 1); } private static int findPosition(int find, List<Integer> lastElement) { int position = 0; int start = 0; int end = lastElement.size() - 1; boolean isElementBiggest = true; while (start <= end) { int middle = (end - start) / 2 + start; if (lastElement.get(middle) <= find) { position = middle; start = middle + 1; } else { end = middle - 1; isElementBiggest = false; } } if (isElementBiggest) { position = lastElement.size(); // Means element is biggest, Create new entry in lastElement list } else if (lastElement.get(position) < find) { // Replace next biggest element not smallest one, // So if element at "position" is "smaller than find_element", Increase position by one position++; //Example : {1,8,4} //Two subjects : {1} and {1,8} //Now for element 4 , position will be 0 where 1 < 4 means replace 4 with 8 not with 1 //Final output : {1} and {1,4} } return position; } } |
Output :
|
1 2 3 4 5 6 |
3 1 4 6 3 6 |