A drilling rig pulls n core samples from a mineshaft, recording each sample's density in the order it was extracted (top of the shaft first). A sinking run is any subsequence of samples (not necessarily adjacent) read in extraction order whose densities are strictly decreasing. Report the greatest number of samples a sinking run can contain.
Line 1: an integer n.
Line 2: n space-separated integers, the densities in extraction order.
A single integer: the length of the longest strictly decreasing subsequence.
Example 1
Input
6 2 9 4 6 3 1
Expected
4
Explanation
One longest strictly decreasing run is 9, 6, 3, 1 using 4 samples; no run of 5 strictly decreasing samples exists.
Example 2
Input
4 1 2 3 4
Expected
1
Explanation
Densities only increase, so no two samples form a decreasing run; the best is a single sample.
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 →