# Longest Increasing Subsequence

Learn about another variation of the string-based problems that are solved using dynamic programming.

## We'll cover the following

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

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.