# HelloKoding

Practical coding guides

# Longest Increasing Subsequence

In this article, you will learn to resolve the longest increasing subsequence problems by using a dynamic programming algorithm

A longest increasing subsequence (LIS) is obtained from a sequence, has elements in increasing order and as long as possible

## Problem 1: Find length of LIS

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

## 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

• Using 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 the current element based on its value is greater than the previous element or not, respectively

LISLengthByBruteForce.java

``````package com.hellokoding.algorithm;

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])

LISLengthByDPBottomUp.java

``````package com.hellokoding.algorithm;

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: Find LIS

• 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.1: Dynamic programming

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

LISByDPBottomUp.java

``````package com.hellokoding.algorithm;

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