candies - interviewstreet

Question

Alice is a teacher of kindergarten. She wants to give some candies to the children in her class. All the children sit in a line and each of them has a rating score according to his or her usual performance. Alice wants to give at least 1 candy for each children. Because children are somehow jealousy. Alice must give her candies according to their ratings subjects to for any adjacent 2 children if one's rating is higher than the other he/she must get more candies than the other. Alice wants to save money so she wants to give as few as candies in total.

Input

The first line of the input is an integer N, the number of children in Alice's class. Each of the following N lines contains an integer indicates the rating of each child.

Output

On the only line of the output print an integer describing the minimum number of candies Alice must give.

Sample Input

3
1
2
2

Sample Output

4

Explanation

The number of candies Alice must give are 1,2 and 1.

Constraints:

N and the rating of each children is no larger than 10^5.

Can anyone please help me?

Answer 1

You can do this in two passes. Start with everyone having one candy.

First loop i from 1 to n-1 (zero based), if rating[i] > rating[i-1] then candies[i] = candies[i-1]+1

Then loop i from n-2 to 0; if rating[i] > rating[i+1] then candies[i] = max(candies[i], candies[i+1]+1)

It's pretty easy to show this gives you a valid distribution of candies, since the second loop can't break anything fixed by the first, and all possible rating discrepancies must be caught by one of the two loops. It's not as obvious that this will use the minimum number of candies, but if you examine each assignment closely you can show that the conditions prove a lower bound on the number of candies required (by a particular individual) at each step.