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
``````6
``````
• Time complexity: O(2n) 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 lisi, lisj are length of the LIS at index i and j

lisi = max(lisi, lisj + 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
``````6
``````
• Time complexity: O(n2) 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++) {
}

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

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(n2) as you use 2 for-loop

• Space complexity: O(n2) as you use 2D array to cache the increasing subsequences