Proficient Level
Implement the method longestIncreasingSubsequence that returns the length of the longest strictly increasing subsequence.
A subsequence keeps original order but may skip elements. The chosen values must be strictly increasing.
The task is designed to test careful handling of edge cases, not only the most common input.
- Use only the first
sizeelements. - Return the length, not the subsequence itself.
- Equal values cannot extend a strictly increasing subsequence.
Example 1
Input
nums (int[]) =
[10,9,2,5,3,7,101,18]size (int) =
8Returns (int)
4Example 2
Input
nums (int[]) =
[0,1,0,3,2,3]size (int) =
6Returns (int)
4Example 3
Input
nums (int[]) =
[7,7,7,7]size (int) =
4Returns (int)
1Let dp[i] be the best subsequence length ending at index i, then extend from earlier smaller values.
Ready to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run