# Untitled

unknown
python
2 years ago
1.3 kB
14
Indexable
Never
```"""

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)
```