Facebook PixelLongest Increasing Subsequence — Coding Practice
Longest Increasing SubsequenceMedium

Longest Increasing Subsequence

Medium 20.4k52% acceptance
ArrayDynamic ProgrammingBinary Search

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

A subsequence is formed by deleting zero or more elements without changing the order of the remaining ones. "Strictly increasing" means each chosen element is greater than the one before it.

Example 1
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
One longest increasing subsequence is [2,3,7,101] (or [2,3,7,18]), of length 4.
Example 2
Input: nums = [0,1,0,3,2,3]
Output: 4
[0,1,2,3] is increasing and has length 4.
Example 3
Input: nums = [7,7,7,7,7]
Output: 1
Equal values are not strictly increasing, so the best is a single element.
Constraints
  • 1 ≤ nums.length ≤ 2500
  • -10⁴ ≤ nums[i] ≤ 10⁴
Asked atGoogleMicrosoftAmazonMeta
JavaScript
Loading editor…
Case 1
[10,9,2,5,3,7,101,18]
expected: 4
Case 2
[0,1,0,3,2,3]
expected: 4
Case 3
[7,7,7,7,7]
expected: 1
Case 4
[1]
expected: 1
Case 5
[4,10,4,3,8,9]
expected: 3
Case 6
[5,4,3,2,1]
expected: 1
Case 7
[1,3,6,7,9,4,10,5,6]
expected: 6