Longest Increasing Subsequence
Updated
Problem statement
Given an integer array nums, return the length of its longest strictly increasing subsequence.
A subsequence keeps the original order but may skip elements. Strictly increasing means that every chosen value is greater than the previous chosen value.
Function
lengthOfLIS(nums: int[]) → intExamples
Example 1
nums = [10,9,2,5,3,7,101,18]return = 4One longest increasing subsequence is [2,3,7,18], which has length 4. No increasing subsequence has length 5.
Example 2
nums = [3,3,3]return = 1Equal values cannot extend a strictly increasing subsequence, so the maximum length is 1.
Constraints
1 <= nums.length <= 100000.-1000000 <= nums[i] <= 1000000.
More Angel One Phone Screen questions
Similar questions at other companies
- Longest Increasing SubsequenceByteDance · PHONE SCREENByteDance interview questions
- Longest Increasing SubsequenceSalesforce · PHONE SCREENSalesforce interview questions
- Split Array to Minimize the Largest SumNation with NaMo · PHONE SCREEN
- Maximum Profit in Job SchedulingAmazon · PHONE SCREEN
- Minimize the Largest Part BeautyAdobe · PHONE SCREENAdobe interview questions
- Longest Increasing Price SubsequenceOpenAI · OAOpenAI interview questions
- Minimum Cost to Attend Required CoursesVisa · OAVisa interview questions
- Fill a Time Window with SongsMicrosoft · OAMicrosoft interview questions
- Maximum Taxi EarningsWells Fargo · OAWells Fargo interview questions
- Longest Increasing Subsequence from Two ArraysSquarepoint Capital · OASquarepoint Capital interview questions