(LIS) Longest Increasing Subsequence Algorithm

Question

EDIT
Finally, I found this "Brute force" method is not right.
So I write another two methods to solve the LIS problem.

• Using LCS on the original array and the sorted array. Time complexity = (n^2).
• Using DP + Binary search. Time complexity = O(nlgn).

[The code is at the end.]

---

I try to use brute force to find Longest Increasing Subsequence (LIS). But personally I think the time complexity of this algorithm is O(n²), which is equal to the DP approach, is it correct?

// Find LIS Brute force.
public static int[] findLIS_BF (int[] givenArray) {
    int size = givenArray.length;
    int maxLen = Integer.MIN_VALUE;
    int prevIndex = 0;
    int tempLen = 1;
    int head = 0;
    for (int tempHead = 0; tempHead < size; tempHead ++) {
        prevIndex = tempHead;
        tempLen = 1;
        for (int subPointer = tempHead + 1; subPointer < size; subPointer ++) {
            if (givenArray[prevIndex] <= givenArray[subPointer]) {
                prevIndex = subPointer;
                tempLen ++;
            }
        }
        if (tempLen > maxLen) {
            maxLen = tempLen;
            head = tempHead;
        }
    }

    System.out.println("LIS by BF, max len = " + maxLen);
    int[] rest = new int[maxLen];
    int restIndex = 0;
    rest[restIndex] = givenArray[head];
    restIndex ++;
    prevIndex = head;
    for (int i = head + 1; i < size; i ++) {
        if (givenArray[prevIndex] <= givenArray[i]) {
            rest[restIndex] = givenArray[i];
            restIndex ++;
            prevIndex = i;
        }
    }
    return rest;
}

---

[EDIT]
[LCS Method]

public class FindLIS_LCS {

// Find LIS by LCS.
// Time complexity = O(n^2).
// LCS.
// Time complexity = O(n^2).
// Note:
// UP LEFT MARK = -1.
// UP MARK = -2.
// LEFT MARK = -3.
private static int LCS (int[] firstA, int[] secondA, int[][]c, int[][]b) {
    int lenFA = firstA.length;
    int lenSA = secondA.length;

    // Init c matrix.
    for (int i = 0; i < lenFA; i ++) c[i][0] = 0;
    for (int i = 0; i < lenSA; i ++) c[0][i] = 0;

    for (int i = 1; i < lenFA+1; i ++) {
        for (int j = 1; j < lenSA+1; j ++) {
            if (firstA[i - 1] == secondA[j - 1]) {
                c[i][j] = c[i - 1][j - 1] + 1;
                b[i - 1][j - 1] = -1;
            } else if (c[i - 1][j] >= c[i][j - 1]) {
                c[i][j] = c[i - 1][j];
                b[i - 1][j - 1] = -2;
            } else {
                c[i][j] = c[i][j - 1];
                b[i - 1][j - 1] = -3;
            }
        }
    }
    return c[lenFA][lenSA];
}

// Print out the LCS.
// Time complexity = O(m + n).
private static void printLCS_Helper (int[] firstA, int[][]b, int i, int j) {
    if (i < 0 || j < 0) return; // Base case.
    if (b[i][j] == -1) {
        printLCS_Helper(firstA, b, i - 1, j - 1);
        System.out.print(String.format("%-6d", firstA[i]));
    } else if (b[i][j] == -2) printLCS_Helper(firstA, b, i - 1, j);
    else printLCS_Helper(firstA, b, i, j - 1);
}
public static void printLCS (int[] firstA, int[][]b) {
    int size = firstA.length;
    printLCS_Helper(firstA, b, size - 1, size - 1);
}

// Quick sort for array.
// Time complexity = O(nlgn).
private static void exchange (int[] givenArray, int firstIndex, int secondIndex) {
    int temp = givenArray[firstIndex];
    givenArray[firstIndex] = givenArray[secondIndex];
    givenArray[secondIndex] = temp;
}
private static int partition (int[] givenArray, int start, int end, int pivotIndex) {
    int pivot = givenArray[pivotIndex];
    int left = start;
    int right = end;
    while (left <= right) {
        while (givenArray[left] < pivot) left ++;
        while (givenArray[right] > pivot) right --;
        if (left <= right) {
            exchange(givenArray, left, right);
            left ++;
            right --;
        }
    }
    return left;
}
private static void quickSortFromMinToMax_Helper (int[] givenArray, int start, int end) {
    if (start >= end) return; // Base case.
    // Generate a random num in the range[start, end] as the pivot index to partition the array.
    int rand = start + (int) (Math.random() * ((end - start) + 1));
    int split = partition (givenArray, start, end, rand);
    // Do recursion.
    quickSortFromMinToMax_Helper(givenArray, start, split - 1);
    quickSortFromMinToMax_Helper(givenArray, split, end);
}
public static void quickSortFromMinToMax (int[] givenArray) {
    int size = givenArray.length;
    quickSortFromMinToMax_Helper(givenArray, 0, size - 1);
}

// Copy array.
public static int[] copyArray (int [] givenArray) {
    int size = givenArray.length;
    int[] newArr = new int[size];
    for (int i = 0; i < size; i ++) 
        newArr[i] = givenArray[i];
    return newArr;
}

// Main method to test.
public static void main (String[] args) {
    // Test data: {1, 2, 1, 4, 5, 3, 10}.
    //int[] givenArray = {1, 2, 1, 4, 5, 3, 10};
    int[] givenArray = {2, 1, 6, 3, 5, 4, 8, 7, 9};
    int size = givenArray.length;
    // Test finding LIS by LCS approach.
    int[] sortedArr = copyArray(givenArray);
    quickSortFromMinToMax (sortedArr);
    int[][]c = new int[size + 1][size + 1];
    int[][]b = new int[size][size];
    System.out.println("Test max len = " + LCS(givenArray, sortedArr, c, b));
    printLCS(givenArray, b);
}
}

[DP + Binary Search Method]

public class FindLIS {

// Linear search.
public static int linearSearch (int[] givenArray, int key) {
    int size = givenArray.length;
    for (int i = size - 1; i >= 0; i --) {
        if (givenArray[i] >= 0) 
            if (givenArray[i] < key) return i;
    }
    return -1;
}

// Find the len of the LIS.(Longest increasing (non-necessarily-adjacent) subsequence).
// DP + Binary search.
// Time complexity = O(nlgn).
// Note:
// This binary search to find the elem's index of the given array, which is less than the elem's value = key.
private static int biSearch (int[] givenArray, int start, int end, int key) {
    if (start > end) return -1;
    int mid = (start + end) / 2;
    if (givenArray[mid] <= key) return mid;
    else return biSearch(givenArray, start, mid - 1, key);
}

public static int findLISLen (int[] givenArray) {
    int size = givenArray.length;
    int maxLen = 1;
    int[] memo = new int[size];
    for (int i = 0; i < size; i ++) memo[i] = -10;
    memo[0] = givenArray[0];

    for (int i = 1; i < size; i ++) {
        if (givenArray[i] > memo[maxLen - 1]) {
            memo[maxLen] = givenArray[i];
            maxLen ++;
        } else {
            // int pos = linearSearch(memo, givenArray[i]); // Using linear search, the time complexity = O(n^2).
            int pos = biSearch(memo, 0, maxLen - 1, givenArray[i]); // Using Binary search, the time complexity = O(nlgn).
            memo[pos + 1] = givenArray[i];
        }
    }
    // Show memo.
    showArray(memo);
    return maxLen;
}


// Show array.
public static void showArray (int[] givenArray) {
    int size = givenArray.length;
    for (int i = 0; i < size; i ++) 
        System.out.print(String.format("%-6d", givenArray[i]));
    System.out.println();
}

// Main method to test.
public static void main (String[] args) {
    // Test data: {2, 1, 6, 3, 5, 4, 8, 7, 9}.
    //int[] givenArray = {2, 1, 6, 3, 5, 4, 8, 7, 9};
    //int[] givenArray = {1, 2, 1, 4, 5, 3, 10};
    int[] givenArray = {2, 1, 6, 3, 5, 4, 8, 7, 9};

    // Test finding the LIS by DP + Binary search.
    System.out.println("Test finding the LIS by DP + Binary search, max len = " + findLISLen(givenArray));

}
}

Answer 1

Yes your approach and both DP approach are of complexity O(n^2). For O(nlogn) algorithm refer here It also gives implementation.

Answer 2

Try this Approach in Java.. Uses the Inbuilt TreeSet of Java.. so it is less error prone and faster to implement..

//an efficient way to find longest increasing sub sequence O(nlogn)
//using the inbuilt TreeSet
import java.io.*;
import java.util.*;

public class LISEfficient {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();    //number of elements
        int[] ar = new int[n];     //input elements
        for (int i=0; i<n; i++) {
            ar[i] = sc.nextInt();
        }

        System.out.println(lis2(ar));       //returns the size of LIS
    }

    static int lis2(int[] ar){
        TreeSet<Integer> set = new TreeSet<Integer>();
        for (int i=0; i<ar.length; i++) {
            Integer ceil = set.ceiling(ar[i]);
            if(ceil == null)     //if ceil not present this simply extends the current sequence
                set.add(ar[i]);
            else{                   //replace ceil with this value
                set.remove(ceil);
                set.add(ar[i]);
            }
        }
        return set.size();
    }
}