300. Longest Increasing Subsequence
Given an integer array nums, return the length of the longest strictly increasing subsequence.
Example 1:
Input: nums = [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Example 2:
Input: nums = [0,1,0,3,2,3] Output: 4
Example 3:
Input: nums = [7,7,7,7,7,7,7] Output: 1
Constraints:
1 <= nums.length <= 2500-104 <= nums[i] <= 104
Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?
Asked at top 20 of 30 companies
TCS
Google
InfosysTopics
Similar problems
Increasing Triplet SubsequenceMediumRussian Doll EnvelopesHardMaximum Length of Pair ChainMediumNumber of Longest Increasing SubsequenceMediumMinimum ASCII Delete Sum for Two StringsMediumMinimum Number of Removals to Make Mountain ArrayHardFind the Longest Valid Obstacle Course at Each PositionHardMinimum Operations to Make the Array K-IncreasingHardLoading editor…
1class Solution:
2 def lengthOfLIS(self, nums: List[int]) -> int:
3
Starter codePython 3Spaces: 4
Loading editor…
1class Solution:
2 def lengthOfLIS(self, nums: List[int]) -> int:
3
Starter codePython 3Spaces: 4
Examples
Input
[10,9,2,5,3,7,101,18]
Input
[0,1,0,3,2,3]
Input
[7,7,7,7,7,7,7]
Your code is saved on this device.Solution