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:
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 , 0); int k = 1; for(int i = 1 ; i < cap ; i++){ if(ratings[i] > ratings[i - 1]){ candy[i] = max(k++ , candy[i]); }else{ k = 1; } } k = 1; for(int i = cap -2 ; i >= 0 ; i --){ if(ratings[i] > ratings[i + 1]){ candy[i] = max(k++ , candy[i]); }else{ k = 1; } } int ans = cap; for(int i = 0 ; i < cap ; i++) ans += candy[i]; return ans; } };
原文：http://www.cnblogs.com/code-swan/p/4139696.html