Find the length of longest increasing subsequence in an array

Algorithm/Insights

This problem can be solved by applying dynamic programming strategy as explained below:
1. Create an array lisLength, of length same as input array length, to store longest increasing subsequence defined as:
   lisLength[i] = length of longest increasing subsequence in the array [0..i] including ith element
2. Initialize lisLength[i] to 1.
3. The lisLength array is then updated one element by element:
   lisLength[i] = Max(lisLength[j]) + 1, for all values of j where input[j] < input[i] and j < i

How this works:
For j = 0 to i-1, if input[j] < input[i], then input[i] can be added to the longest increasing subsequence which is formed from array elements 0 to j.
Therefore, to find longest increasing subsequence in 0..i, lisLength[i], we need the Max(lisLength[j]) value which satisfies this condition.
If there is no such j, then longest increasing subsequence in input array 0..i, lisLength[i] = 1 which is formed by adding only ith element.

Example:


lisLength[] : [1, 0, 0, 0, 0, 0, 0, 0]

i = 1: lisLength[1] = 1
    j = 0: input[0] = 12 < input[1] = 18, also lisLength[1] = 1 < lisLength[0] + 1 = 2, so we update:
        lisLength[1] = lisLength[0] + 1 = 2
lisLength[] : [1, 2, 0, 0, 0, 0, 0, 0]

i = 2: lisLength[2] = 1
    j = 0: input[0] = 12 > input[2] = 7
    j = 1: input[1] = 18 > input[2] = 7
lisLength[] : [1, 2, 1, 0, 0, 0, 0, 0]

i = 3: lisLength[3] = 1
    j = 0: input[0] = 12 < input[3] = 34, also lisLength[3] = 1 < lisLength[0] + 1 = 2, so we update:
        lisLength[3] = lisLength[0] + 1 = 2
    j = 1: input[1] = 18 < input[3] = 34, also lisLength[3] = 2 < lisLength[1] + 1 = 3, so we update:
        lisLength[3] = lisLength[1] + 1 = 3
    j = 2: input[2] =  7 < input[3] = 34, but lisLength[3] = 3 > lisLength[2] + 1 = 2, so lisLength is not updated.
lisLength[] : [1, 2, 1, 3, 0, 0, 0, 0]

i = 4: lisLength[4] = 1
    j = 0: input[0] = 12 < input[4] = 30, also lisLength[4] = 1 < lisLength[0] + 1 = 2, so we update:
        lisLength[4] = lisLength[0] + 1 = 2
    j = 1: input[1] = 18 < input[4] = 30, also lisLength[4] = 2 < lisLength[1] + 1 = 3, so we update:
        lisLength[4] = lisLength[1] + 1 = 3
    j = 2: input[2] =  7 < input[4] = 30, but lisLength[4] = 3 > lisLength[2] + 1 = 2, so lisLength is not updated.
    j = 3: input[3] = 34 > input[4] = 30
lisLength[] : [1, 2, 1, 3, 3, 0, 0, 0]

i = 5: lisLength[5] = 1
    j = 0: input[0] = 12 < input[5] = 28, also lisLength[5] = 1 < lisLength[0] + 1 = 2, so we update:
        lisLength[5] = lisLength[0] + 1 = 2
    j = 1: input[1] = 18 < input[5] = 28, also lisLength[5] = 2 < lisLength[1] + 1 = 3, so we update:
        lisLength[5] = lisLength[1] + 1 = 3
    j = 2: input[2] =  7 < input[5] = 28, but lisLength[5] = 3 > lisLength[2] + 1, so lisLength is not updated.
    j = 3: input[3] = 34 > input[5] = 28
    j = 4: input[4] = 30 > input[5] = 28
lisLength[] : [1, 2, 1, 3, 3, 3, 0, 0]

i = 6: lisLength[6] = 1
    j = 0: input[0] = 12 < input[6] = 90, also lisLength[6] = 1 < lisLength[0] + 1 = 2, so we update:
        lisLength[6] = lisLength[0] + 1 = 2
    j = 1: input[1] = 18 < input[6] = 90, also lisLength[6] = 2 < lisLength[1] + 1 = 3, so we update:
        lisLength[6] = lisLength[1] + 1 = 3
    j = 2: input[2] =  7 < input[6] = 90, but lisLength[6] = 3 > lisLength[2] + 1, so lisLength is not updated.
    j = 3: input[3] = 34 < input[6] = 90, also lisLength[6] = 3 < lisLength[3] + 1 = 4, so we update:
        lisLength[6] = lisLength[3] + 1 = 4
    j = 4: input[4] = 30 < input[6] = 90, but lisLength[6] = 4 = lisLength[4] + 1, so lisLength is not updated.
    j = 5: input[5] = 28 < input[6] = 90, but lisLength[6] = 4 = lisLength[5] + 1, so lisLength is not updated.
lisLength[] : [1, 2, 1, 3, 3, 3, 4, 0]

i = 7: lisLength[7] = 1
    j = 0: input[0] = 12 < input[7] = 88, also lisLength[7] = 1 < lisLength[0] + 1 = 2, so we update:
        lisLength[7] = lisLength[0] + 1 = 2
    j = 1: input[1] = 18 < input[7] = 88, also lisLength[7] = 1 < lisLength[1] + 1 = 3, so we update:
        lisLength[7] = lisLength[1] + 1 = 3
    j = 2: input[2] =  7 < input[7] = 88, but lisLength[7] = 3 > lisLength[2] + 1, so lisLength is not updated.
    j = 3: input[3] = 34 < input[7] = 88, also lisLength[7] = 3 < lisLength[3] + 1 = 4, so we update:
        lisLength[7] = lisLength[3] + 1 = 4
    j = 4: input[4] = 30 < input[7] = 88, but lisLength[7] = 4 = lisLength[4] + 1, so lisLength is not updated.
    j = 5: input[5] = 28 < input[7] = 88, but lisLength[7] = 4 = lisLength[5] + 1, so lisLength is not updated.
    j = 6: input[6] = 90 > input[7] = 88
lisLength[] : [1, 2, 1, 3, 3, 3, 4, 4]

Solution: Maximum value in lisLength array = 4.

Time complexity of this solution is O(n^2).

Here is a solution with O(nlogn) complexity:
Longest Increasing Subsequence O(nlogn) solution

Code Snippet

			
package com.ideserve.questions.saurabh;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * Find the length of longest increasing subsequence in an array
 *
 * @author Saurabh
 */
public class LongestIncreasingSubsequence {

    public static int longestIncreasingSubsequence(int[] input) {

        if(input == null || input.length == 0) {
            return 0;
        }

        int n = input.length;
        // lisLength[i] = Length of Longest Increasing Subsequence in input[0..i]
        int[] lisLength = new int[n];
        int maxLength = 1;
        lisLength[0] = 1;
        for (int i = 1; i < n; i++) {
        	lisLength[i] = 1;
            for (int j = 0; j < i; j++) {
                if (input[i] > input[j] && lisLength[i] < lisLength[j] + 1) {
                    lisLength[i] = lisLength[j] + 1;
                }
            }
            // Update the length of longest increasing subsequence found till now
            if(maxLength < lisLength[i]) {
                maxLength = lisLength[i];
            }
        }
        return maxLength;
    }

    public static void main(String[] args) {
        int[] array = { 12, 18, 7, 34, 30, 28, 90, 88 };
        System.out.println("Length of Longest Increasing Subsequence: " + longestIncreasingSubsequence(array));
    }
}
		

Order of the Algorithm

Time Complexity is O(n^2)
Space Complexity is O(n)