FastPrep
Problem · Array

Longest Increasing Subsequence

Learn this problem
● MediumSalesforceFULLTIMEPHONE SCREEN
See Salesforce hiring insights

Problem statement

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

A subsequence is formed by deleting zero or more elements without changing the relative order of the remaining elements.

Function

lengthOfLIS(nums: int[]) → int

Examples

Example 1

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

One longest strictly increasing subsequence is [2, 3, 7, 101], which has length 4.

Example 2

nums = [0,1,0,3,2,3]return = 4

The subsequence [0, 1, 2, 3] is strictly increasing and has the maximum possible length.

Example 3

nums = [7,7,7,7,7,7,7]return = 1

Equal values cannot both appear in a strictly increasing subsequence, so the maximum length is 1.

Constraints

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

More Salesforce problems

drafts saved locally
public int lengthOfLIS(int[] nums) {
  // write your code here
}
nums[10,9,2,5,3,7,101,18]
expected4
checking account