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:
1、Each child must have at least one candy.
2、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 n = ratings.size();
        vector<int> cans(n,1);
        
        for(int i=1;i<n;i++)
        {
            if(ratings[i]>ratings[i-1])
                cans[i] = cans[i-1] + 1;
        }
        for(int i=n-2;i>=0;i--)
        {
            if(ratings[i]>ratings[i+1]&&cans[i]<=cans[i+1])
                cans[i] = cans[i+1] + 1;
        }
        int result = 0 ;
        for(int i=0;i<n;i++)
        {
            result += cans[i];
        }
        return result;
    }
};