Untitled

"""

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.

test_cases = [
    ([1,0,2], 5),
    ([1,2,2], 4),
]

[2,1,2] => 5
[1,2,1] => 4

child i = 1
left < child i < right cand[i] = max(cand[i-1], cand[i+1]) + 1
"""


def solution(ratings):
    cand = [1 for _ in ratings]
    
    sorted_ratings = [[rating, i] for i, rating in enumerate(ratings)]
    sorted_ratings.sort()
    
    for rating, i in sorted_ratings:
        neighbor_candies = []
        
        if i - 1 >= 0 and ratings[i-1] < rating: # left neighbor
            neighbor_candies.append(cand[i-1])
        if i + 1 < len(ratings) and ratings[i+1] < rating: # right neighbor
            neighbor_candies.append(cand[i+1])
        
        if neighbor_candies:
            cand[i] = max(neighbor_candies) + 1

    return sum(cand)



test_cases = [
    ([1,0,2], 5),
    ([1,2,2], 4),
]

for test_case, ans in test_cases:
    print(solution(test_case) == ans)