N children standing in a line with some rating value. You want to distribute minimum number of candies to these children such that each child must have at least one candy and the children with higher rating will have more candies than his neighbour.
Write a program to calculate the minimum candies you must give.
- Input: An array
arrof N integers representing the ratings of each student
Input: arr = [1, 2, 2] Output: 4 Explanation: You can distribute to the first, second and third child 1, 2 and 1 candies respectively. The third child gets 1 candy because it satisfies the above two conditions.
Input: arr = [1, 5, 2, 1] Output: 7 Explanation: Candies given = [1, 3, 2, 1]