There are N children standing in a straight line, and we have a job to distribute candies to all of them.
There are 2 rules to follow:
1. Each child must receive at least 1 candy each.
2. Child having higher rating than its neighbour must receive more candies than it's neighbour.
We have to find out minimum number of candies needed.
a = [5, 5, 4, 3, 2, 1]
answer = 16
candies = [1, 5, 4, 3, 2, 1]
The problem can be approached in a greedy manner.
The idea is that we start by giving 1 candy to each child. If there exists a child which has a higher rating than it's neighbour, we give additional candy to her, otherwise we get away with giving only 1 candy.
We make 2 passes, first from left to right, and second from right to left, distributing candies such that the rules hold true.
1. Initialise each child with 1 candy.
2. Move from left to right, looking for a child which as higher rating than it's previous child.
3. If found, give him 1 more candy than it's previous child.
4. Move from right to left, looking for a child which has higher rating than its next child.
5. If found, give him 1 more candy than the child next to her.