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.

&nbsp;
Example 1:

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


Example 2:

Input: ratings = [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.


&nbsp;
Constraints:


	n == ratings.length
	1 &lt;= n &lt;= 2 * 104
	0 &lt;= ratings[i] &lt;= 2 * 104


class Solution:
    def candy(self, ratings: List[int]) -> int:
        n=len(ratings)
        temp = [1]*n

        for i in range(1,n):
            if(ratings[i]>ratings[i-1]):
                temp[i]=temp[i-1]+1
        if(n>1):
            if(ratings[0]>ratings[1]):
                temp[0]=2

        for i in range(n-2,-1,-1):
            if(ratings[i]>ratings[i+1] and temp[i]<=temp[i+1]):
                temp[i]=temp[i+1]+1

        return sum(temp)
class Solution {
    public int candy(int[] ratings) {

        int[] left = new int[ratings.length];
        Arrays.fill(left, 1);

        // we are checking from left to right that if the element next to our current element has greater rating, if yes then we are increasing their candy
        for(int i = 0; i<ratings.length-1; i++){
            if(ratings[i] < ratings[i+1])
                left[i+1] = left[i]+1;
        }

        int[] right = new int[ratings.length];
        Arrays.fill(right, 1);

        //we are checking from right to left if the element after than our current element is greater or not , if yes then we are also checking their candies if greater rating has less number of candies then increasing their candy
        for(int i = ratings.length -2; i>=0; i--){
            if(ratings[i+1] < ratings[i] && right[i] <= right[i+1])
                right[i] = right[i+1]+1;
        }
        int sum = 0;
        for(int i = 0; i<right.length; i++){
            sum += Math.max(right[i], left[i]);
        }

    return sum;}
}
class Solution {
public:
    int candy(vector<int>& ratings) {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        int ans = 0, i;
        vector<int> store(ratings.size(), 1);
        for (i = 0; i < ratings.size()-1; i++) if(ratings[i+1] > ratings[i]) store[i+1] = store[i]+1;
        for (i = ratings.size()-1; i > 0; i--) if(ratings[i-1] > ratings[i]) store[i-1] = max(store[i-1], store[i]+1);
        for (auto i:store) ans += i;
        return ans;
    }
};
/**
 * @param {number[]} ratings
 * @return {number}
 */
var candy = function(ratings) {
    const n = ratings.length;    
    
    let candies = [...Array(n)].fill(1);
 
    let index = 0;
    let copy = [ratings[0]];
    
    let isDecreasing = true;
    for(let i = 1; i < n; i++) {
        if (ratings[i] > ratings[i - 1]) {
            isDecreasing = false;
            break;
        }
        /* In case of decreasing sequence, make a copy of the current rating, but in inverted format */
        copy.unshift(ratings[i]);
    }
    
    if (isDecreasing) {
        ratings = copy;
    } else {
        copy = [];
    }
    
    while(index >= 0) {
        
        if (index >= n) {
            break;
        }

        if (ratings[index] > ratings[index + 1] && candies[index + 1] >= candies[index]) {            
            candies[index] = candies[index] + 1;            
            index = Math.max(-1, index - 2);
        }
        else if (ratings[index] > ratings[index - 1] && candies[index - 1] >= candies[index]) {            
            candies[index] = candies[index - 1] + 1;
        }

        index++;
     }

    
    return candies.reduce((sum, candy) => sum + candy, 0);
}
Candy