Longest Increasing Subsequence
Easy
Given an integer array nums, return the length of the longest strictly increasing subsequence.
A subsequence is a sequence that can be formed by deleting some or none of the elements of the array without changing the order of the remaining elements.
Example 1
Input
n = 8 nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output
4
Explanation
One longest increasing subsequence is:
[2, 3, 7, 101]
Its length is 4.
Example 2
Input
n = 6 nums = [0, 1, 0, 3, 2, 3]
Output
4
Explanation
One longest increasing subsequence is:
[0, 1, 2, 3]
Its length is 4.
Constraints
1 <= nums.length <= 2500
-10^4 <= nums[i] <= 10^4
A subsequence must maintain the original order.
The subsequence must be strictly increasing.
Hints:
Hint 1
Let dp[i] represent the length of the longest increasing subsequence ending at index i.
Hint 2
For every previous index j:
if nums[j] < nums[i]
dp[i] = max(dp[i], dp[j] + 1)
Auto
Loading editor...
Input
Expected Output