Longest Increasing Subsequence

In this article we will find the length of the Longest Increasing Subsequence (LIS) for any array given to us. What is the LIS? It is the array of integers from the given array in increasing order with the condition that all the elements of LIS should be contiguous.

Example:

The above array has non-increasing elements. The LIS from it will be:

The output is five (the length of the LIS).

There are many methods of differing complexity to find the length of LIS.

Memoize Method

In this method we will use a memoize array to calculate certain values so that further along we can use those already calculated lengths. Using that length, the current element position can be counted into the length of the LIS.

Technique:

We will first take a memoize array of the same length as the given array (considering the length of LIS can be the same as the given array).
We will initialize each index value with one, as the smallest length of LIS will be one. Then we can traverse over the array and keep checking for each element such that the current element’s LIS will be populated in the memoize array. We then finally traverse the whole memoize array to find the max elements that will be our output. This can be better explained using the algorithm below.

Algorithm

Step 1: Initialize mem[length_of_givenArray], back and front

Step 2: traverse array using two Iteration

First Iteration: front=0 to length_of_givenArray-1

Second Iteration: back =0 to front -1

Step3: if Array[back] is less than Array[front]

Update Mem[front] with Max(Mem[front],Mem[back]+1)

Explanation for 3rd Step:

See till the current index (front) value the length of LIS will be either the max of already calculated Length at current index(front) and max Length calculated at index (back) +1. Our aim is to get the maximum of both.

Repeat Step 3 until back is lesser than front

Step4: Traverse mem array and return the maximum value it contains.

Complexity Analysis:

Space: O(N), we are taking extra space to memoize.
Time Complexity: O(N²), two iterations over an array.

Java Implementation

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
class LIS_Class {
  public static int LISMemoize(int LISArray[]) {
    int mem[] = new int[LISArray.length];

    for (int i = 0; i < LISArray.length; i++)
      mem[i] = 1;

    int i = 0, j = 1;

    for (; j < LISArray.length; j++)
      for (i = 0; i < j; i++) {
        if (LISArray[i] < LISArray[j]) {
          mem[j] = Math.max(mem[j], mem[i] + 1);
        }

      }
    int maxLIS = mem[0];
    for (i = 1; i < LISArray.length; i++) {
      maxLIS = Math.max(mem[i], maxLIS);
    }

    return maxLIS;
  }
  public static void main(String[] args) {
    int LISArray[] = {
      15,
      -1,
      8,
      2,
      5,
      11,
      7,
      10
    };

    System.out.println(LISMemoize(LISArray));
  }
}

Code Snippet:

Efficient Approach

In this technique we will use a different strategy to reduce the time complexity. Unlike the above method we will take each element and traverse over a given array only once, but we will take an extra array where we are going to calculate the LIS and then return the length of that new array. In this approach we will check for the best position for a current element where we can place it in the new array, which can increase our chances of getting the LIS.

Suppose the current element we are processing for LIS is two. That means two should be placed in a position where our chances of getting LIS will be max, as the lesser the number kept in the LIS array, the more other elements we can place after it.

At the end of the traversal we will have the LIS. But the point is how we can find the place or correct position of the current element from the given array to the LIS array. Here we will use a binary search to find the upper bound which will give us the (-(index)-1)value, which is a negative value where index is a position where we can place our current element. We can achieve this in Log(N) time which makes this algorithm efficient.

Algorithm

Step 1: Initialize array binLIS of same length of given array
IndexOfLIS=0

Initialize LISArray[0]=givenArray[0]

Step 2: Iterate over given array

Step 3: If current element of givenArray[currentIndex] > binLIS[last_Ele]

Then place currElement at end of binLIS array and goto step 2

Else

Find the best position of givenArray[cuuIndex] using
Arrays.binarySearch(binLIS,strtIndex,endIndex,givenArr[curIndx]

Where startIndex : 0
endIndex: indexOfLIS

Place the currentElement at position got from BinarySearch

Step 4: Return the Last index of LIS array

Complexity Analysis

Space Complexity: O(N), as we are taking an extra array for storing LIS.
Time Complexity: O(NlogN), N for traversing over given array and LogNfor finding the correct position for a new element using binary search.

Java Implementation

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
import java.util.*;
class LIS_Class {
  public static int binaryLIS(int LISArray[]) {
    int binArr[] = new int[LISArray.length];
    binArr[0] = LISArray[0];
    int index = 1;
    for (int i = 1; i < LISArray.length; i++) {

      if (binArr[index - 1] < LISArray[i]) {
        binArr[index] = LISArray[i];
        index++;
      } else {
        int indexWhereCurrELe = Arrays.binarySearch(binArr, 0, index - 1, LISArray[i]);

        if (indexWhereCurrELe < 0) {
          indexWhereCurrELe = indexWhereCurrELe * (-1);
          indexWhereCurrELe--;
        }

        binArr[indexWhereCurrELe] = LISArray[i];

      }

    }
    return index;
  }
  public static void main(String[] args) {
    int LISArray[] = {

      15,
      -1,
      8,
      2,
      5,
      11,
      7,
      10,
      20
    };

    System.out.println(binaryLIS(LISArray));
  }
}

Code Snippet: