Longest Increasing Subsequence in Java

In this article, we will learn to resolve the longest increasing subsequence problems by using brute-force and dynamic programming algorithms

A longest increasing subsequence (LIS) is obtained from a sequence, has elements in increasing order, and as long as possible. The LIS does not necessarily have to be contiguous or unique, one sequence may have multiple increasing subsequences

Problem 1

Given an unsorted array of numbers a
Write an algorithm to find the length of the longest increasing subsequence (LIS)

Example 1

Input: [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]
Output: 6
Explanation: The LIS is {0, 2, 6, 9, 11, 15}. It's not contiguous or unique. Other instances are {0, 2, 6, 9, 13, 15}, {0, 4, 6, 9, 11, 15, {0, 4, 6, 9, 13, 15}

Approach 1.1: Brute force with recursion

This approach uses recursion to scan the increasing subsequences of all elements in the given array to find the length of the longest one. At each iteration, there are two options: count or not count the current element based on its value is greater than the previous element or not
The implementation steps of the recursion algorithm follow
- Create a recursion function lengthOfLIS with the 3 input parameters: the given array A[n], prevIndex, and currentIndex
- Base case of the recursion: return to 0 if currentIndex has reached to the end of the array
- Declare two variables: included and excluded. If current element A[currentIndex] greater than previous element A[prevIndex] or prevIndex == -1 (the first element of the array must always be included in the count), update included variable value to 1 + lengthOfLIS(A, currentIndex, currentIndex + 1). Otherwise, set excluded value to lengthOfLIS(A, previousIndex, currentIndex + 1)
- Return the max value of included and excluded variable and close the function
- Run the function lengthOfLIS for the given array, starting at prevIndex = -1 and currentIndex = 0

public class LISLengthByBruteForce {  
    static int lengthOfLIS(int[] a, int prevIndex, int currIndex) {
        if (currIndex == a.length) {
            return 0;
        }

        int included = 0;
        if (prevIndex < 0 || a[currIndex] > a[prevIndex]) {
            included = 1 + lengthOfLIS(a, currIndex, currIndex+1);
        }

        int excluded = lengthOfLIS(a, prevIndex, currIndex+1);

        return Math.max(included, excluded);
    }

    public static void main(String[] args) {
        int[] arr = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
        System.out.println(lengthOfLIS(arr, -1, 0));
    }
}

Output

Time complexity: O(2ⁿ) as you have to iterate over all elements in the array and each element has 2 options
Space complexity: O(1)

Approach 1.2: Dynamic programming

Optimal substructure and overlapping subproblems: say lis_i, lis_j are length of the LIS at index i and j

lis_i = max(lis_i, lis_j + 1), ∀0 <= j < i and a[i] > a[j]
Use an array cache[n] to cache the length of the LIS at each index corresponding with the given array a[n]
Bottom-up filling cache[n] with the base case

cache[i] = 1, ∀0 <= i < n
LIS(a[n]) = max(cache[n])

import java.util.Arrays;

public class LISLengthByDPBottomUp {  
    static int lengthOfLIS(int[] a) {
        if (a.length == 0) {
            return 0;
        }

        int[] cache = new int[a.length];
        Arrays.fill(cache, 1);

        for (int i = 1; i < a.length; i++) {
            for (int j = 0; j < i; j++) {
                if (a[i] > a[j]) {
                    cache[i] = Math.max(cache[i], cache[j] + 1);
                }
            }
        }

        return Arrays.stream(cache).max().getAsInt();
    }


    public static void main(String[] args) {
        int[] arr = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
        System.out.println(lengthOfLIS(arr));
    }
}

Output

Time complexity: O(n²) as you use 2 for-loop
Space complexity: O(n) as you use a cache array which has the same size as the given array

Problem 2

Given an unsorted array of numbers a
Write an algorithm to find the longest increasing subsequence (LIS)
The LIS does not necessarily have to be contiguous or unique

Example 2

Input: [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]
Output: [0, 2, 6, 9, 11, 15]
Explanation: The LIS is {0, 2, 6, 9, 11, 15}. It's not contiguous or unique. Other instances are {0, 2, 6, 9, 13, 15}, {0, 4, 6, 9, 11, 15, {0, 4, 6, 9, 13, 15}

Approach 2: Dynamic programming

Optimal substructure and overlapping subproblems same as the previous approach of problem 1

import java.util.ArrayList;  
import java.util.List;

public class LISByDPBottomUp {  
    static List<Integer> findLIS(int[] arr) {
        List<List<Integer>> cache = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            cache.add(new ArrayList<>());
        }

        cache.get(0).add(arr[0]);

        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j] && cache.get(i).size() < cache.get(j).size() + 1) {
                    cache.set(i, new ArrayList<>(cache.get(j)));
                }
            }
            cache.get(i).add(arr[i]);
        }

        List<Integer> longest = cache.get(0);
        for (int i = 0; i < cache.size(); i++) {
            if (longest.size() < cache.get(i).size()) {
                longest = new ArrayList<>(cache.get(i));
            }
        }

        return longest;
    }

    public static void main(String[] args) {
        int[] arr = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
        System.out.println(findLIS(arr).toString());
    }
}

Output

[0, 2, 6, 9, 11, 15]

Time complexity: O(n²) as you use 2 for-loop
Space complexity: O(n²) as you use 2D array to cache the increasing subsequences

Algorithm Dynamic Programming