# Longest Increasing Subsequence

Let's solve the Longest Increasing Subsequence problem using Dynamic Programming.

## Statement

The **Longest Increasing Subsequence (LIS)** is the longest subsequence from a given array in which the subsequence elements are sorted in strictly increasing order. Given an integer array, `nums`

, find the length of the LIS in this array.

Let’s say we have an integer array [6, 9, 8, 2, 3, 5, 1, 4, 7], and we want to get the longest increasing subsequence in this array. There are multiple increasing subsequences of different lengths, such as [6, 9], [6, 8], [2, 3, 5], [2, 3, 5, 7], and so on. The longest increasing subsequences, in this case, are [2, 3, 4, 7] and [2, 3, 5, 7], both of length 4.

**Constraints:**

- $1 \leq$
`nums.length`

$\leq 6000$ - $-10^9 \leq$
`nums[i]`

$\leq 10^9$

## Examples

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