Facebook Pixel

You are on level: Student

0%
Expand section
Expand section
Expand section
Expand section
Expand section
Expand section
Expand section
Expand section
Expand section
Expand section
Expand section

Longest Increasing Subsequence

Given an array of integers, find the length of the longest subsequence whose elements appear in strictly increasing order. A subsequence keeps the relative order of the array but does not have to be contiguous.

Input & Output
Input
nums — the integer sequence
Output
the length of the longest strictly increasing subsequence of nums
Example
Input
nums = [50, 3, 10, 7, 40, 80]
Output
4
Explanation

[3, 7, 40, 80] increases at every step and uses four elements. [3, 10, 40, 80] is another subsequence of the same length, so the answer is the length rather than the subsequence itself.

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

Both [1, 2, 4] and [1, 2, 3] are longest increasing subsequences which have length 3.

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

[2, 3, 7, 101] and [2, 5, 7, 18] both reach length 4. Nothing longer exists because the leading 10, 9 cannot extend any of them.

Constraints
  • 0 <= nums.length <= 2500
  • -10^4 <= nums[i] <= 10^4

Try it yourself

Invest in Yourself
Your new job is waiting. 83% of people that complete the program get a job offer. Unlock unlimited access to all content and features.
Go Pro