## Candy

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?

### Analysis:

Scan the rating array from left to right and then from right to left. In every scan just consider the rising order (l->r: r[i]>r[i-1] or r->l: r[i]>r[i+1]), assign +1 candies to the rising position.
The final candy array is the maximum (max(right[i],left[i])) in each position.
The total candies is the sum of the final candy array.

The time complexity is O(n).

### Code:

class Solution {
public:
int getC(vector<int> &r){
vector<int> lc(r.size(),1);
vector<int> rc(r.size(),1);
int res=0;
for (int i=1;i<lc.size();i++){
if (r[i]>r[i-1]){
lc[i]=lc[i-1]+1;
}
}
for (int i=rc.size()-2;i>=0;i--){
if (r[i]>r[i+1]){
rc[i]=rc[i+1]+1;
}
}
for (int i=0;i<r.size();i++){
res+=max(lc[i],rc[i]);
}
return res;
}

int candy(vector<int> &ratings) {
return getC(ratings);
}
};