Longest Increasing Subsequence

Problem statement

The Longest Increasing Subsequence (LIS) problem requires you to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for {10, 9, 3, 5, 4, 11, 7, 8} is 4 and LIS is {3, 4, 7, 8}.

Solution: Naïve approach

The simplest approach is to try to find all increasing subsequences and then returning the maximum length of the longest increasing subsequence.

• Time complexity : O(${2^n}$)
• Space complexity : O(${2^n}$)

Since the complexity is going to be exponential once again, we need an optimized solution. We can solve this problem using the dynamic programming approach.

Solution: Dynamic programming

Before moving on to the implementation, let’s look at the recurrence relation.

• Let arr[0..n-1] be the input array and LIS(i) be the length of the LIS ending at index i such that arr[i] is the last element of the LIS.
• LIS(i) = 1 + max{ LIS(j) } where 0 < j < i and arr[j] < arr[i]
• LIS(i) = 1, if no such j exists
• To find the LIS for a given array, we need to return max(LIS(i)), where 0 < i < n.

Formally, the length of the longest increasing subsequence ending at index i will be 1 greater than the maximum of lengths of all longest increasing subsequences ending at indices before i, where arr[j] < arr[i] (j < i). Thus, we see that the LIS problem satisfies the optimal substructure property as the main problem can be solved using solutions to subproblems.

Let’s move on to the implementation now.