COCI '10 Contest 6 #2 Uspon

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 32M

Problem types

Tomislav has recently discovered that he's completely out of shape. He actually becomes tired while walking down the stairs! One morning he woke up and decided to come in good shape. His favourite sport is cycling, so he decided to ride a tour on the local hills.

The route he is taking is described as a sequence of N numbers which represent the height of the road at evenly spaced points of the route, from the beginning to the end of it. Tomislav is interested in the largest segment of the route which goes up the hill he has to ride, according to the information he has. Let's call such a segment a 'climb'. Tomislav is too tired to bother about details, so he will only take into account the height difference of a climb, not its length.

A climb is more strictly defined as a consecutive increasing subsequence of at least two numbers describing the road. The size of the climb is the difference between the last and first number in the subsequence.

For example, let's consider a route described by the following sequence of heights: 12\ \underline{3\ 5\ 7\ 10}\ 6\ \underline{1\ 11}. Underlined numbers represent two different climbs. The size of the first climb is 7. The second climb is larger, with size 10. Points with heights 12 and 6 are not parts of any climb.

Help Tomislav and calculate the largest climb!

Input Specification

The first line of input contains a positive integer N (1 \le N \le 1\,000), the number of measured points on the route.

The second line of input contains N positive integers P_i (1 \le P_i \le 1\,000), the heights of measured points on the route.

Output Specification

The first and only line of output should contain the size of the largest climb. If the route in the input does not contain any climbs, output 0.

Sample Input 1

1 2 1 4 6

Sample Output 1


Sample Input 2

12 20 1 3 4 4 11 1

Sample Output 2


Explanation for Sample Output 2

Climbs are 12-20, 1-3-4, and 4-11. 1-3-4-4-11 is not a climb because a sequence of numbers describing a climb has to be strictly increasing.

Sample Input 3

10 8 8 6 4 3

Sample Output 3



There are no comments at the moment.