[LeetCode] 135. Candy

Problem : https://leetcode.com/problems/candy/

Step 1, initially give every child 1 candy

Step 2, iterate from left to right. If child on right side has higher rating than child on left side,  child on right side be given1 more candy than child on left.

Step 3, iterate from right to left. If child on left side has higher rating than child on right side and child on left has less candy, child on left side be given 1 more candy than child on right.

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

        for i in range(len(ratings) - 1):
            if ratings[i+1] > ratings[i]:
                candies[i+1] = candies[i] + 1
        
        for i in reversed(range(1, len(ratings))):
            if ratings[i-1] > ratings[i]:
                candies[i-1] = max(candies[i-1], candies[i] + 1)
        
        return sum(candies)