**Solution**

**Candy** https://leetcode.com/problems/candy/

- Move from left to right. If ratings[i] > ratings[i-1], then candy[i] = candy[i-1]+1.
- Move from right to left. If ratings[i] > ratings[i+1], then candy[i] = max(candy[i], candy[i+1]+1)
- Proof - Sketch all 3 combinations with 2 ratings. The method gives right answer. Now add third rating and sketch all 6 combinations. Still get the right answer.

http://stackoverflow.com/questions/11292913/candies-interviewstreet

```
class Solution(object):
def candy(self, ratings):
"""
:type ratings: List[int]
:rtype: int
"""
N = len(ratings)
candy = [1]*N
for i in range(1, N):
if ratings[i] > ratings[i-1]:
candy[i] = candy[i-1] + 1
for i in range(N-2, -1, -1):
if ratings[i] > ratings[i+1]:
candy[i] = max(candy[i], candy[i+1]+1)
return sum(candy)
```