Skip to main content
All Questions

Longest Increasing Subsequence

Medium
Unlock detailed company stats for this questionUpgrade
Given an integer array, find the length of the longest strictly increasing subsequence (not necessarily contiguous).

Given an integer array nums, return the length of its longest strictly increasing subsequence. A subsequence keeps the original order of the elements but can skip some of them.

Example 1

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

One longest increasing subsequence is [2, 3, 7, 101].

Example 2

Input: nums = [7, 7, 7, 7] Output: 1

The values have to strictly increase, so the longest subsequence is a single element.

Constraints

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

Related courses

Course

Machine Learning Engineer Interview Prep

Land your dream machine learning role at Meta, Google, Amazon, Apple, Microsoft, Nvidia, and other top companies. Learn from mock interviews, frameworks, and advice from senior candidates. Explore ML system design, core concepts, coding, behavioral interviews, and more.

Course

Behavioral Interviews: A Practical Guide for Engineers

Get offers at the level you deserve. Prep for senior+ behavioral interviews at FAANG and Tier-1 companies. Made with staff and principal engineers from Meta, Netflix, Google, and more. Avoid downleveling, elevate past projects, and stop sounding like a robot.