135. Candy

// There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

// 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.
// Return the minimum number of candies you need to have to distribute the candies to the children.

// Input: ratings = [1,0,2]
// Output: 5
// Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.


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

        for (int i= n-1; i>0 ; i--)
	      {
		    if(ratings[i-1]>ratings[i])
			   nums[i-1]=max(nums[i]+1,nums[i-1]);
	      }
        
        int sum=0;
        for(int i=0; i<nums.size(); i++){
            sum+=nums[i];
        }
        
        return sum;
        
    }
};