There are N children standing in a line. Each child is assigned a rating value.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.What is the minimum candies you must give?

 1 public class Solution { 2     public int candy(int[] ratings) { 3         if (ratings==null || ratings.length==0) return 0; 4         int[] left = new int[ratings.length]; 5         int[] right = new int[ratings.length]; 6         int sum = 0; 7         for (int i=0; i<left.length; i++) { 8             if (i == 0) left[i] = 1; 9             else if (ratings[i] > ratings[i-1]) left[i] = left[i-1] + 1;10             else left[i] = 1;11         }12         for (int j=right.length-1; j>=0; j--) {13             if (j == right.length-1) right[j] = 1;14             else if (ratings[j] > ratings[j+1]) right[j] = right[j+1] + 1;15             else right[j] = 1;16         }17         for (int k=0; k<left.length; k++) {18             left[k] = Math.max(left[k], right[k]);19             sum += left[k];20         }21         return sum;22     }23 }