Practice
JavaScriptData StructuresReactConcepts
Sign in
← Back to problems

Longest Increasing Subsequence

Dynamic Programmingmedium

Implement `lengthOfLIS(nums)` returning the length of the longest strictly increasing subsequence.

Sample tests

Input: lengthOfLIS([10,9,2,5,3,7,101,18])
Output: 4
Input: lengthOfLIS([0,1,0,3,2,3])
Output: 4

+ 1 hidden test run on Submit.

Hints

Common pitfalls
  • The O(n^2) DP is fine here; a patience-sorting variant is O(n log n).

Learning resources

  • Wikipedia: Dynamic programming
Approach & explanation (try first)

The per-index DP gives the LIS length in O(n^2) time.

Loading...
⌘/Ctrl + Enter

Run your code to see results.