231. Longest Increasing Subsequence

Hard · Dynamic Programming

Given an unsorted array of integers, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence derived from the array by deleting some or no elements without changing the order of the remaining elements.

Examples

Example 1
Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
Explanation: LIS is [2, 3, 7, 101] or [2, 3, 7, 18]

Example 2
Input: nums = [0, 1, 0, 3, 2, 3]
Output: 4
Explanation: [0,1,2,3]

Constraints

• 1 ≤ n ≤ 2500
• -10⁴ ≤ nums[i] ≤ 10⁴