Longest Increasing Subsequence

The key idea

Let dp[i] be the length of the longest increasing subsequence that ends at index i. Each dp[i] is 1 plus the best dp[j] over every earlier j with nums[j] < nums[i]. The answer is the largest value in dp. A faster O(n log n) method keeps a tails array where tails[k] is the smallest possible tail of any increasing subsequence of length k+1.

Problem

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence you can derive from nums by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of [0,3,1,6,2,2,7]. The chosen elements must be strictly increasing, meaning each one is larger than the one before it.

Constraints

1 <= nums.length <= 2500
-10^4 <= nums[i] <= 10^4

Examples

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

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

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

Complexity

Time: O(n^2) Space: O(n)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →