Given an array of n integers, return the length of its longest strictly increasing subsequence.
A subsequence is obtained by deleting zero or more elements without changing the order of the remaining elements. "Strictly increasing" means each chosen element is greater than the one before it. You must return only the length, which is uniquely determined even when several subsequences achieve it.
Line 1: a single integer n (the array length).
Line 2: n space-separated integers. This line is absent when n = 0.
A single line containing one integer: the length of the longest strictly increasing subsequence. For an empty array the answer is 0.
For a = [10, 9, 2, 5, 3, 7, 101, 18] one longest strictly increasing subsequence is [2, 3, 7, 18] (or [2, 3, 7, 101]), so the length is 4.
Example 1
Input
8 10 9 2 5 3 7 101 18
Expected
4
Explanation
A longest strictly increasing subsequence is [2, 3, 7, 18] of length 4; no strictly increasing subsequence is longer.
Example 2
Input
6 7 7 7 7 7 7
Expected
1
Explanation
All elements are equal, so no element is strictly greater than another; the longest strictly increasing subsequence is any single element, of length 1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →