How should I practice Longest Increasing Subsequence?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Microsoft onsite interview problems in FastPrep.

Is Longest Increasing Subsequence associated with Microsoft?

FastPrep tags this as a Microsoft onsite interview coding practice problem when the problem catalog has that company and stage context.

Longest Increasing Subsequence

Microsoft● MediumNEW GRADONSITE INTERVIEW

Learn

Problem statement

Return the length of the longest subsequence of nums whose values are strictly increasing. A subsequence preserves original index order but may omit values.

Function

lengthOfLIS(nums: int[]) → int

Examples

Example 1

nums = [10,9,2,5,3,7,101,18]return = 4

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

Constraints

1 <= nums.length <= 200000
-10^9 <= nums[i] <= 10^9