135. Candy

time: O(n)

space: O(n)

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
 
*/