HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Linear Data Structures: Arrays > problem:


50419 - The longest bitonic sequence

Guest
• Review clarifications (3)

Section problems

• 50395 - Page "Like" Averages
• 50410 - Zero Padding
• 50329 - Draw Matrix-1
• 50337 - Exam Averages
• 50334 - What is the class average?
• 50383 - Noisy Mornings
• 51129 - Hexagon
• 51097 - Sum of Borders
• 50419 - The longest bitonic seq...
• 50420 - Teachers Sightseeing
• 50344 - Profit or Loss
• 50431 - Sultan's Game
• 50445 - Cryptography
• 51246 - Swap largest word, reverse ...
• 50516 - Lines
• 50446 - Snake
• 50345 - Orders

Feedback

If you notice incorrect translations in Contester, please let author know.

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.

Для отправки решений необходимо выполнить вход.

www.contester.ru