61. Longest Increasing Subsequence

Medium · Dynamic Programming

Given an array of integers, find the length of the longest strictly increasing subsequence. A subsequence is derived from the array by deleting some or no elements without changing the order of the remaining elements.

For example, in the array [10, 9, 2, 5, 3, 7, 101, 18], the longest increasing subsequence is [2, 3, 7, 101] with length 4.

Examples

Example 1
Input: [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
Explanation: The longest increasing subsequence is [2, 3, 7, 101] with length 4. Other valid LIS include [2, 3, 7, 18].
Example 2
Input: [0, 1, 0, 4, 4, 4, 3, 5, 1]
Output: 4
Explanation: The longest increasing subsequence is [0, 1, 4, 5] with length 4.

Constraints