# 135. Candy

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MhsT1iqkYMCM2OaGqJx%2F-MhvLaPA5chMvZTyoAHB%2Fimage.png?alt=media\&token=db93ae96-1ffc-4d73-9beb-98c53ff8f6bc)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MhsT1iqkYMCM2OaGqJx%2F-MhvLf2MJKzFGsM3xblt%2Fimage.png?alt=media\&token=636fd123-bdff-4623-b528-853511a6b393)

time: O(n)

space: O(n)

```java
class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int candy[] = new int[n];
        Arrays.fill(candy, 1);
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i-1]) {
                candy[i] = Math.max(1, candy[i-1]+1);
            }
        }
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i+1]) {
                candy[i] = Math.max(candy[i], candy[i+1]+1);
            }
        }
        int sum = 0;
        for (int c : candy) {
            sum += c;
        }
        return sum;
        // return Arrays.stream(candy).sum();
    }
}

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

look from left first 
1,   0,  2  [ratings]

1,   1,  1  [candy]
---------------------
1,   1,  1  [candy] 
i-1  i

1,   1,  1to2
    i-1  i 
----------------------

look from right
1,      1,  2  [candy]
        i   i+1

1to2,   1,  2 
       i+1
i
 
*/
```