Skip to main content

Longest Increasing Subsequence

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

Problems39 / 152
Sign in

Longest Increasing Subsequence

MEDIUMArrayBinary Search

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

Example 1

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

Example 2

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

Use DP: dp[i] = length of LIS ending at index i. For each i, check all previous j where nums[j] < nums[i] and update dp[i] = max(dp[i], dp[j] + 1).

Draft saves automatically

Loading editor...

Submit also runs hidden tests
nums =
[10,9,2,5,3,7,101,18]
Expected
4
Run with your own input (JSON)