LeetCode OJ - Candy

 1 /**
 2      * There are N children standing in a line. Each child is assigned a rating value.
 3      * You are giving candies to these children subjected to the following requirements:
 4      * Each child must have at least one candy.
 5      * Children with a higher rating get more candies than their neighbors.
 6      * What is the minimum candies you must give?
 7      * @param ratings
 8      * @return
 9      */
10     public int candy(int[] ratings)
11     {
12         int N = ratings.length;
13         int[] candy = new int [N]; //who get how many candies
14         int[] left = new int[N]; //left[i] presents the number of consecutive ratings (in left side of i) smaller than ratings[i]
15         int[] right = new int[N]; //right[i] presents the number of consecutive ratings (in right side of i) smaller than ratings[i] 
16         
17         //by DP, caculating the left and right
18         left[0] = 0;
19         for(int i=1;i<N;i++)
20             left[i] = ratings[i]>ratings[i-1]? left[i-1]+1:0;
21         right[N-1] = 0;
22         for(int i=N-2;i>=0;i--)
23             right[i] = ratings[i]>ratings[i+1]? right[i+1]+1:0;
24         //decide how many candies each one should get
25         int r = 0; 
26         for(int i=0;i<N;i++)
27         {
28             //the local minimum
29             if(left[i] == 0 && right[i] == 0)
30                 candy[i] = 1;
31             //the local maximum
32             if(left[i]!=0 && right[i]!=0)
33                 candy[i] = Math.max(left[i], right[i])+1;
34             //other cases
35             else 
36                 candy[i] = left[i]!=0? left[i]+1:right[i]+1;
37             r =r+candy[i];
38         }
39         return r;
40     }