There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:
- Each child must have at least one candy.
- Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?
class Solution { public: int candy(vector<int> &ratings) { int cap = ratings.size(); int *candy = new int[cap]; fill(candy, candy + cap, 1); for(int i = 1; i < cap; i++) { if(ratings[i] > ratings[i-1]) candy[i] = candy[i-1] + 1; } for(int i = cap - 2; i >= 0; i--) { if(ratings[i] > ratings[i+1]) candy[i] = max(candy[i], candy[i+1] + 1); } int res = 0; for(int i = 0; i < cap; i++) res += candy[i]; delete candy; return res; } };