Longest Increasing Subsequence
Problem statement
Given an integer array nums, return the length of its longest strictly increasing subsequence.
A subsequence keeps some of the elements in their original order, possibly skipping others; the kept elements do not have to be next to each other. Strictly increasing means every kept element is larger than the one before it, so equal values cannot both be used.
Function
lengthOfLIS(nums: int[]) → intExamples
Example 1
nums = [6,1,8,3,9,4,12,5]return = 4The subsequences [1, 3, 4, 5] and [1, 8, 9, 12] both strictly increase and have length 4. No longer one exists: the array splits into the neighbouring pairs (6, 1), (8, 3), (9, 4) and (12, 5), and in each pair the larger value comes first, so an increasing subsequence can use at most one value from each pair. The answer is 4.
Example 2
nums = [7,7,7,7]return = 1The values must strictly increase, so two equal values cannot both be used. The answer is 1.
Example 3
nums = [4,-1,0,3,-5,2,3]return = 4The subsequence [-1, 0, 2, 3] uses the values at indices 1, 2, 5, 6 and strictly increases, so the answer is 4. The elements do not have to be next to each other.
Constraints
1 <= nums.length <= 2500-10^4 <= nums[i] <= 10^4