All problems

Longest Increasing Subsequence

Medium · dynamic programming

Given a list of integers nums, return the length of the longest strictly increasing subsequence.

A subsequence keeps the original order but may skip elements, so [2, 5, 7] is a subsequence of [2, 9, 5, 3, 7]. "Strictly increasing" means each chosen number must be larger than the one before it, so equal numbers cannot sit next to each other in the subsequence. You only return the length, not the subsequence itself.

Examples

Example 1

Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]

Output: 4

One longest choice is [2, 3, 7, 101]. Another is [2, 5, 7, 18]. No increasing choice has 5 numbers.

Example 2

Input: nums = [0, 1, 0, 3, 2, 3]

Output: 4

Take 0, 1, 2, 3 (the 2 and the last 3 are at indices 4 and 5).

Example 3

Input: nums = [7, 7, 7, 7, 7]

Output: 1

Equal numbers do not count as increasing, so the best you can do is one number.

Constraints