 All Problems
Longest Increasing Subsequence
medium
array
binary search
dynamic programming
amazon
google
microsoft
facebook

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

Example 1:

Input:  10 9 2 5 3 7 101 18
Output: 4

([2, 3, 7, 101])

Example 2:

Input:  0 1 0 3 2 3
Output: 4

Constraints:

  • 1 ≤ nums.length ≤ 2500
  • -10⁴ ≤ nums[i] ≤ 10⁴

Follow-up: Can you achieve O(n log n)?

Input format: Space-separated integers.

Output format: Length of LIS.

Run to check your code against the sample cases, or submit to run every case