Loading...
Loading...
Loading...
Divya has her scores from n mock placement tests, in the order she took them. She wants to show her progress, so she picks some of the tests, keeping their order, so that each picked score is strictly higher than the one before it. The picked tests do not have to be next to each other.
Print the largest number of tests she can pick.
Example 1
Input
8 10 9 2 5 3 7 101 18
Output
4
One best pick is 2, 3, 7, 18. No pick of 5 tests goes strictly up.
Example 2
Input
5 7 7 7 7 7
Output
1
Equal scores are not strictly higher, so only one test can be picked.
Try the problem first. Open one hint at a time.
Let len[i] be the most tests in a pick that ends exactly at test i.
Test i can follow any earlier test j with a smaller score. So len[i] = 1 + the largest len[j] over those j, or 1 if there is none.
The best pick can end at any test, so the answer is the largest len[i], not len[n].
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor