Dynamic Programming
Given a sequence of integers A, find the maximum length of a bitonic subsquence of A.
A bitonic sequence is one that is first increasing and then decreasing. Namely,
a sequence A[0:n] is called "bitonic" if there exists an i such that
A[0:i] is an increasing sequence, and A[i:n] is a decreasing sequence.
Input has two lines; first line is a single number that is the n.
Second line has n numbers separated by space
which is the array A[0:n].
Expected output is a single line consisting of
a single number that should be the maximum
bitonic subsequence of A[0:n].
Examples
Example 1:
Input
3
15 78 -12
Output
3
Explanation:
[15, 78, -12] is a bitonic subsequence, and it's the longest
Example 2:
Input
10
-78 117 131 -136 182 -96 -23 -97 -200 49
Output
7
Explanation:
[-78, 117, 131, 182, -23, -97, -200] is a bitoinic subsequence of A[0:10] of size 7.
No bitonic subsequence is longer.