public int candy(int[] ratings) {
if (ratings == null  ratings.length == 0) return 0;
int n = ratings.length;
// a[i] stores the num of candies of ith kid
int[] a = new int[n]; a[0] = 1;
// scan from left to right
for (int i = 1; i < n; i++)
a[i] = (ratings[i] > ratings[i  1]) ? a[i  1] + 1 : 1;
// scan from right to left
int sum = a[n  1];
for (int i = n  2; i >= 0; i) {
if (ratings[i] > ratings[i + 1])
a[i] = Math.max(a[i], a[i + 1] + 1);
sum += a[i];
}
return sum;
}
Java O(n) solution


Hi mo10, when we scan from left to right, we make sure that the kid who has higher rating on the right always has (at least) one more candy than the kid on his/her lefthand side.
When we scan from right to left, notice that we use Math.max( ) to make sure that the number of candy will not decrease, so that it won't break what we have done in the first scan.
If you want to ask why we need to scan from right to left? We can take a look at the following example, let's say we have some kids and their ratings are:
[1, 2, 5, 4, 3, 2, 1]
after scan from left to right, we get the following candies for each kid:
[1, 2, 3, 1, 1, 1, 1]
as you can see the kid who has rating 4 should have more candies than the kid who has rating 3, to fix that, we need to scan from right to left, finally we get the candies:
[1, 2, 5, 4, 3, 2, 1]