A survey sled records n sand-height readings across a dune field, in travel order. A peak profile is a subsequence of readings (not necessarily adjacent), in travel order, whose heights strictly increase up to a single peak reading and then strictly decrease. A purely strictly-increasing subsequence counts as a peak profile (its peak is the last reading), and so does a purely strictly-decreasing one (its peak is the first reading). A single reading is a peak profile of length 1. Report the maximum number of readings in a peak profile.
Line 1: an integer n.
Line 2: n space-separated integers, the heights in travel order.
A single integer: the length of the longest bitonic subsequence.
Example 1
Input
7 1 4 3 7 4 2 5
Expected
5
Explanation
The peak profile 1, 4, 7, 4, 2 strictly rises to the peak 7 then strictly falls, using 5 readings, which is the most possible here.
Example 2
Input
5 1 2 3 4 5
Expected
5
Explanation
The heights only rise, which is a valid peak profile (peak at the end) using all 5 readings.
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 →