Time limit 2000/4000/4000/4000 ms. Memory limit 2000/64000/15000/15000 Kb.
Question by Ilir Capuni.
The longest bitonic sequence
A sequence of integers whose values first increase
and reach the peek, and then decrease is called bitonic.
In this problem, we are looking at bitonic sequences
of a given sequence.
Note: Increasing (and decreasing)
doesn't include equal to. When it's increasing, the current
number is definitely greater than the previous number.
Example:
The sequence 1 2 4 6 8 7 5 4 3 2 1 is bitonic, with
number 8 being the peek. A sequence of this sequence
is, say 1 6 5 1, but 8 2 6 is not a sequence.
Suppose that you are given an array of integers.
You need to find the length of the longest bitonic
sequence of the given sequence.
Question:
Write a program that gets as an input a positive
number n and a sequence of n integers and computes
the length of the longest bitonic sequence.
Input specification
You will be given an integer number (n) at the
beginning where 1 ≤ n ≤ 50000.
Then, in the following line, you will be given n integers
which are between -10000 and 10000.
Output specification
Show just one integer: length of the longest bitonic sequence.
Sample Input I
6
3 0 1 4 2 -1
|
Sample Input II
14
4 2 1 5 7 3 1 4 7 8 2 1 3 2
|
Sample Output I
5
|
Sample Output II
6
|
Explanation for Sample Input 2: The longest
bitonic sequence is: 1 4 7 8 2 1 with the length 6.
Для отправки решений необходимо выполнить вход.
|