readings, in the order they arrived. An analyst wants to cross out some entries so that the remaining ones are strictly increasing, while keeping as many entries as possible. The remaining entries keep their original order, but they don't have to be adjacent in the original array.
Return the largest number of entries that can be kept.
An O(n²) solution is straightforward; see if you can get to O(n log n).readings=[4, 12, 3, 6, 5, 9, 1] → 3
You can pick 4, 6, 9 or 3, 5, 9, which is length 3. There are no four strictly rising values in order.
readings=[-2, 0, 0, 1, -5, 2] → 4
-2, 0, 1, 2 gives length 4. The two zeros cannot both be used, because the rise must be strict.
readings=[5, 5, 5] → 1
All values are equal, so only one of them can be picked.
readings=[4, 12, 3, 6, 5, 9, 1]
3
Run checks the first 3 tests in your browser. Submit checks all 136 tests on the server, hidden ones included.