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?

Idea: scan twice: find out the inversion and

correct the number of candies for the corresponding child.

class Solution {
public:
    int candy(vector<int> &ratings) {
        int n= ratings.size();
        if (n==0)  return 0;
        int total=0;
        vector<int> res(n,1);
        for (int i=1; i<n; i++)
        {
            if (ratings[i]>ratings[i-1])
            {
                res[i]=res[i-1]+1;
            }
        }
       
        for (int i=n-2; i>=0; i--)
        {
            if (ratings[i]>ratings[i+1]&&res[i]<=res[i+1])
            {
                res[i]=res[i+1]+1;
            }
        }
       
        for (int j=0; j<n; j++)
        {
           total+=res[j];
        }   
       
        return total;
    }
};