Longest Bitonic Subsequence
mediumDynamic Programming II+20 XPTime limit 2s
A trek's altitude readings are listed in order. A bitonic subsequence first goes strictly up and then strictly down — like climbing a hill and coming back. Either part may be empty, so a purely increasing or purely decreasing subsequence also counts. Find the length of the longest bitonic subsequence.
Input:
- line 1:
n - line 2:
nintegers
Output: the length of the longest bitonic subsequence.
Constraints: 1 ≤ n ≤ 2000, −10⁹ ≤ values ≤ 10⁹.
Example: in 1 11 2 10 4 5 2 1 one answer is 1 2 10 4 2 1 (length 6).
Think about it: for every index i, compute inc[i] = the longest strictly increasing subsequence ending at i, and dec[i] = the longest strictly decreasing subsequence starting at i (LIS from the right). The peak is some i: answer = max of inc[i] + dec[i] − 1.
Sample input 1
8 1 11 2 10 4 5 2 1
Sample output 1
6
Sample input 2
5 1 2 3 4 5
Sample output 2
5
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).