Longest Increasing Subsequence

September 9, 2018September 9, 2018 by omt

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.

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));
    }
}

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.

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));
    }


}

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.

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;
    }
}

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.

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;
    }


}

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 :

omt Lab

Longest Increasing Subsequence

Related