LeetCode 135 - Candy

[LeetCode] Candy | 程序员达达
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?
X. Approach #3 Using one array

    public int candy(int[] ratings) {
        int[] candies = new int[ratings.length];
        Arrays.fill(candies, 1);
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }
        int sum = candies[ratings.length - 1];
        for (int i = ratings.length - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = Math.max(candies[i], candies[i + 1] + 1);
            }
            sum += candies[i];
        }
        return sum;
    }

X.
https://leetcode.com/articles/candy/#approach-4-single-pass-approach-with-constant-space-accepted

    public int candy(int[] ratings) {
        int sum = 0;
        int[] left2right = new int[ratings.length];
        int[] right2left = new int[ratings.length];
        Arrays.fill(left2right, 1);
        Arrays.fill(right2left, 1);
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                left2right[i] = left2right[i - 1] + 1;
            }
        }
        for (int i = ratings.length - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                right2left[i] = right2left[i + 1] + 1;
            }
        }
        for (int i = 0; i < ratings.length; i++) {
            sum += Math.max(left2right[i], right2left[i]);
        }
        return sum;
    }

http://shanjiaxin.blogspot.com/2014/04/candy-leetcode.html
http://www.programcreek.com/2014/03/leetcode-candy-java/
http://www.cnblogs.com/yrbbest/p/4438782.html

We can always assign a neighbor with 1 more if the neighbor has higher a rating value. However, to get the minimum total number, we should always start adding 1s in the ascending order. We can solve this problem by scanning the array from both sides. First, scan the array from left to right, and assign values for all the ascending pairs. Then scan from right to left and assign values to descending pairs.

    public int candy(int[] ratings) {
        if(ratings == null || ratings.length == 0)
            return 0;
        int len = ratings.length;
        int[] candies = new int[len];
        candies[0] = 1;
        
        for(int i = 1; i < len; i++) {
            if(ratings[i] > ratings[i - 1])
                candies[i] = candies[i - 1] + 1;
            else
                candies[i] = 1;
        }
        
        int sum = candies[len - 1];
        
        for(int i = len - 2; i >= 0; i--) {
            if(ratings[i] > ratings[i + 1])
                if(candies[i] <= candies[i + 1])
                    candies[i] = candies[i + 1] + 1;
            sum += candies[i];
        }
        
        return sum;
    }

https://discuss.leetcode.com/topic/2463/my-accepted-solution-is-quite-neat-but-not-sure-if-can-further-optimize-it

    public int candy(int[] ratings) {

        if(ratings.length < 2) return ratings.length;
        int[] leftTrav = new int[ratings.length];
        int[] rightTrav = new int[ratings.length];
        for(int i=0; i<length; i++) {
            leftTrav[i] = 1;
            rightTrav[i] = 1;
        }
        
        for(int i=0; i<length - 1; i++) {
            int j = (length - 1) - i;
            if(ratings[i+1] > ratings[i]) leftTrav[i+1] = leftTrav[i] + 1;
            if(ratings[j-1] > ratings[j]) rightTrav[j-1] = rightTrav[j] + 1;
        }
        int total = 0;
        for(int i=0; i<length; i++) total += Math.max(leftTrav[i], rightTrav[i]);
        return total;
    }

https://discuss.leetcode.com/topic/25985/simple-o-n-java-solution-with-comments
http://www.cnblogs.com/springfor/p/3877120.html
 1     public int candy(int[] ratings) {  
 2         if(ratings==null || ratings.length==0)
 3             return 0;  
 4           
 5         int[] leftnums = new int[ratings.length];  
 6         int[] rightnums = new int[ratings.length];
 7         
 8         leftnums[0]=1;  
 9         for(int i=1;i<ratings.length;i++){  
10             if(ratings[i]>ratings[i-1])  
11                 leftnums[i] = leftnums[i-1]+1;  
12             else  
13                 leftnums[i] = 1;  
14         }
15         
16         rightnums[ratings.length-1] = leftnums[ratings.length-1];  
17         for(int i=ratings.length-2;i>=0;i--){
18             if(ratings[i]>ratings[i+1]) 
19                 rightnums[i] = rightnums[i+1]+1;
20             else
21                 rightnums[i] = 1;
22                 
23         }
24         
25         int res = 0;
26         for(int i = 0; i<ratings.length; i++)
27             res += Math.max(leftnums[i],rightnums[i]);
28         
29         return res;  
30     } 
https://github.com/AnnieKim/ITint5/blob/master/031_%E5%88%86%E9%85%8D%E7%B3%96%E6%9E%9C.cpp
Solution: 两个方案。可以先尝试写O(n)空间，再看看O(1)空间可不可行。
           面试的时候也不要一上来写难度大的，容易慌，先写简单的再改进，这样思路也更清晰。
 方案 1：O(n)时间，O(n)空间。
         先每人分1个糖果。
         从左向右遍历一遍，如果右边比左边的rating大，就令右边的孩子比左边多一个糖果。
         从右向左遍历一遍，如果左边比右边的rating大，并且糖果数不满足要求，就令左边的孩子比右边多一个糖果。

算法2：初始化所有小孩糖数目为1，从前往后扫描，如果第i个小孩等级比第i-1个高，那么i的糖数目等于i-1的糖数目+1；从后往前扫描，如果第i个的小孩的等级比i+1个小孩高,但是糖的数目却小或者相等，那么i的糖数目等于i+1的糖数目+1。

该算法时间复杂度为O(N)

https://siddontang.gitbooks.io/leetcode-solution/content/greedy/candy.html

    int candy(vector<int> &ratings) {
        vector<int> candys;
        //首先每人发一颗糖
        candys.resize(ratings.size(), 1);
        //这个循环保证了右边高级别的孩子一定比左边的孩子糖果数量多
        for(int i = 1; i < (int)ratings.size(); i++) {
            if(ratings[i] > ratings[i - 1]) {
                candys[i] = candys[i - 1] + 1;
            }
        }

        //这个循环保证了左边高级别的孩子一定比右边的孩子糖果数量多
        for(int i = (int)ratings.size() - 2; i >= 0; i--) {
            if(ratings[i] > ratings[i + 1] && candys[i] <= candys[i + 1]) {
                candys[i] = candys[i + 1] + 1;
            }
        }

        int n = 0;
        for(int i = 0; i < (int)candys.size(); i++) {
            n += candys[i];
        }
        return n;
    }

X. O(1) space Single Pass Approach with Constant Space
https://leetcode.com/articles/candy/#approach-4-single-pass-approach-with-constant-space-accepted

This approach relies on the observation(as demonstrated in the figure below as well) that in order to distribute the candies as per the given criteria using the minimum number of candies, the candies are always distributed in terms of increments of 1. Further, while distributing the candies, the local minimum number of candies given to a student is 1. Thus, the sub-distributions always take the form: $\text{1, 2, 3, ..., n}$ or $\text{n,..., 2, 1}$, whose sum is simply given by $n(n+1)/2$.

Now, we can view the given $rankings$ as some rising and falling slopes. Whenever the slope is rising, the distribution takes the form: $\text{1, 2, 3, ..., m}$. Similarly, a falling slope takes the form: $\text{k,..., 2, 1}$. An issue that arises now is that the local peak point can be included in only one of the slopes. Whether to include the local peak point($\text{n}$) in the rising slope or the falling slope?

In order to decide it, we can observe that in order to satisfy both the right neighbour and the left neighbour criteria, the peak point's count needs to be the max. of the counts determined by the rising and the falling slopes. Thus, in order to determine the number of candies required, the peak point needs to be included in the slope which contains more number of points. The local valley point can also be included in only one of the slopes, but this issue can be resolved easily, since the local valley point will always be assigned a candy count of 1(which can be subtracted from the next slope's count calculations).

Coming to the implementation, we maintain two variables $old\_slope$ and $new\_slope$ to determine the occurence of a peak or a valley. We also use $up$ and $down$ variables to keep a track of the count of elements on the rising slope and on the falling slope respectively(without including the peak element). We always update the total count of $candies$ at the end of a falling slope following a rising slope (or a mountain). The leveling of the points in $rankings$ also works as the end of a mountain. At the end of the mountain, we determine whether to include the peak point in the rising slope or in the falling slope by comparing the $up$ and $down$ variables up to that point. Thus, the count assigned to the peak element becomes: $\text{max}(up, down) + 1$. At this point, we can reset the $up$ and $down$ variables indicating the start of a new mountain.

The following figure shows the cases that need to be handled for this example:

rankings: [1 2 3 4 5 3 2 1 2 6 5 4 3 3 2 1 1 3 3 3 4 2]

From this figure, we can see that the candy distributions in the subregions always take the form $\text{1, 2, ...n}$ or $\text{n, ..., 2, 1}$. For the first mountain comprised by the regions $a$ and $b$, while assigning candies to the local peak point($pt. 5$), it needs to be included in $a$ to satisfy the left neighbour criteria. The local valley point at the end of region $b$($pt. 8$) marks the end of the first mountain(region $c$). While performing the calculations, we can include this point in either the current or the following mountain. The $pt. 13$ marks the end of the second mountain due to levelling of the $pt. 13$ and $pt. 14$. Since, region $e$ has more points than region $d$, the local peak($pt. 10$) needs to be included in region $e$ to satisfy the right neighbour criteria. Now, the third mountain $f$ can be considered as a mountian with no rising slope($up=0$) but only a falling slope. Similarly, $pt. 16, 18, 19$ also act as the mountain ends due to the levelling of the points.

https://discuss.leetcode.com/topic/8208/one-pass-constant-space-java-solution

This solution picks each element from the input array only once. First, we give a candy to the first child. Then for each child we have three cases:

1. His/her rating is equal to the previous one -> give 1 candy.
2. His/her rating is greater than the previous one -> give him (previous + 1) candies.
3. His/her rating is less than the previous one -> don't know what to do yet, let's just count the number of such consequent cases.

When we enter 1 or 2 condition we can check our count from 3. If it's not zero then we know that we were descending before and we have everything to update our total candies amount: number of children in descending sequence of raitings - coundDown, number of candies given at peak - prev (we don't update prev when descending). Total number of candies for "descending" children can be found through arithmetic progression formula (1+2+...+countDown). Plus we need to update our peak child if his number of candies is less then or equal to countDown.

    public int candy(int[] ratings) {
        if (ratings == null || ratings.length == 0) return 0;
        int total = 1, prev = 1, countDown = 0;
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] >= ratings[i-1]) {
                if (countDown > 0) {
                    total += countDown*(countDown+1)/2; // arithmetic progression
                    if (countDown >= prev) total += countDown - prev + 1;
                    countDown = 0;
                    prev = 1;
                }
                prev = ratings[i] == ratings[i-1] ? 1 : prev+1;
                total += prev;
            } else countDown++;
        }
        if (countDown > 0) { // if we were descending at the end
            total += countDown*(countDown+1)/2;
            if (countDown >= prev) total += countDown - prev + 1;
        }
        return total;
    }

http://www.allenlipeng47.com/blog/index.php/2016/07/21/candy/
https://discuss.leetcode.com/topic/8208/one-pass-constant-space-java-solution

If current rating is greater than previous one, then current value should be prev + 1

If current rating is equal to previous one, then current value should be 1

If current rating is less than previous one, we don’t know the value yet.

Let’s consider the continuous descending ratings. If there is continuous descending ratings, we will usecountDown to memorize the descending length. Below case, countDown = 2 at curr position.

During a descending order, when curr is equal to previous or greater than previous, we can use progression formula to calculate the descending area size.

Let’s reconsider the prev when calculating size of descending area. Think about below case. Prev is 2, which is not tall enough and makes next 2 elements to 1 and 0.

Let’s reconsider the prev when calculating size of descending area. Think about below case. Prev is 2, which is not tall enough and makes next 2 elements to 1 and 0.

In this case when countDown >= prev, we should increase prev by countDown – prev + 1.

public static int candy(int[] ratings) {
    int pre = 1, countDown = 0, total = 1;
    for (int i = 1; i < ratings.length; i++) {
        if (ratings[i] >= ratings[i - 1]) {
            if (countDown > 0) {
                total += countDown * (countDown + 1) / 2;   // progression part
                if (countDown >= pre) { // check if pre is tall enough
                    total += countDown - pre + 1;
                }
                pre = 1;    // when ascending and there is countDown, prev should be 1
                countDown = 0;
            }
            pre = ratings[i] == ratings[i - 1] ? 1 : pre + 1;   // when equals to previous one, set to 1. Else set to prev + 1
            total += pre;
        }
        else {
            countDown++;
        }
    }
    if (countDown > 0) {    // check if there is countDown in the end
        total += countDown * (countDown + 1) / 2;
        if (countDown >= pre) {
            total += countDown - pre + 1;
        }
    }
    return total;
}

https://discuss.leetcode.com/topic/870/is-there-a-solution-with-o-n-time-and-o-1-space/4

O(1) space的方法来自Discuss里的@shpolsky

1. 这里我们一次遍历数组， 主要使用一个变量countDown来记录遍历时遇到的递减序列
2. 当ratings[i] < ratings[i - 1]时，我们遇到的就是递减序列，这时我们countDown增加一，
3. 否则，ratings[i] >= ratings[i - 1]，大于或者等于这两种情况里，我们都需要对之前遇到的递减情况进行处理
   1. 处理之前含有递减序列的情况
      1. 这里我们用prev这个变量记录了递减序列排头元素peak，有多少块糖
      2. 然后我们利用等差数列求和公式来计算这整个递减序列里我们需要补发多少块糖，countDown是长度n，也是最后一个元素a_n
      3. 之后还要判断，当countDown >= peak的时候，就是这个递减序列里，需要最多块糖的元素和peak的当前糖数比较，假如peak的糖数少，我们要给peak补充countDown - prev + 1块糖，或者理解为把peak所在位置的糖数从 prev 替换为 countDown + 1。
   2. 接下来我们处理一般情况，就是 ratings[i] = ratings[i - 1]时，prev为1，否则prev加1，我们再把prev添加到结果total中
4. 最后也要判断一下，是否数组最后的一部分为递减序列，假如是，则按照之前的代码处理。

    public int candy(int[] ratings) {
        if (ratings == null || ratings.length == 0) return 0;
        int total = 1, prev = 1, countDown = 0;
                    
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] >= ratings[i - 1]) {
                if (countDown > 0) {
                    total += countDown * (countDown + 1) / 2;
if (countDown >= prev) total += countDown - prev + 1;
                    countDown = 0;
                    prev = 1;
                }
                prev = (ratings[i] == ratings[i - 1]) ? 1 : prev + 1;
                total += prev;
            } else countDown++;
        }
        
        if (countDown > 0) {
            total += countDown * (countDown + 1) / 2;
            if (countDown >= prev) total += countDown - prev + 1;
        }
        
        return total;
    }

https://discuss.leetcode.com/topic/48849/simple-java-o-n-time-o-1-space

 * if ratings[i] = ratings[i-1], then give[i] = 1
 * if ratings[i] > ratings[i-1], then give[i] = give[i-1] + 1, give[i] only depends on give[i-1], use cur instead
 * if ratings[i] < ratings[i-1], then give[i] = 1, and
 *  suppose last peak is at p with pv candies given, if i-p < pv, sum += i-j, else sum += i-j+1.
    public int candy(int[] ratings) {
        int ans = 1, cur = 1, p = 0, pv = 1, n = ratings.length;
        for (int i = 1; i < n; i++) {
            if (ratings[i] == ratings[i-1]) {
                p = i;
                ans += pv = cur = 1;
            } else if (ratings[i] > ratings[i-1]) {
                p = i;
                ans += pv = ++cur;
            } else {
                cur = 1;
                ans += i-p < pv ? i-p : i-p+1;
            }
        }
        return ans;
    }

http://fisherlei.blogspot.com/2013/11/leetcode-candy-solution.html
蛮好玩的题。感觉用dp简单点。定义Candy[i]为第i个孩子需要给的最少的糖数， 
那么 
Candy[i] =            Candy[i-1]+1  if ratings[i] > ratings[i-1] 递增序列，后面小孩需要的糖果是前一个小孩的糖果数+1 
                           1                   if ratings[i] == ratings[i-1] 直线，按照题意，如果两个小孩rating一样多，后面的小孩可以只拿一个糖 
                           Candy[i-1] –1 if ratings[i] < ratings[i-1] 递减序列。这个递推式显然是有缺陷，因为如果递减序列比较长的话，Candy[i]就可能出现负值了，负值显然是没有意义的。比如下图为例： 
蓝线是rating变化曲线，数字是Candy[i]的值。基于上面递推式的解（第一行）明显是不合理的。而第二行经过调整的（红色数字），才是最优解。简单的说，就是当遇到一个波谷的时候，调整一下左边的下降序列就好了，但是要注意区分条件，上一个波峰只在有些条件下才需要更改（例一和例二的区别）。 
 
https://leetcode.com/discuss/23835/one-pass-constant-space-java-solution
/*
 方案 2：O(n)时间，O(1)空间。
         不需要记录每个孩子得到的糖果数目，只需要记录前一个孩子得到的糖果数last和
         当前孩子之前rating取极大值的孩子位置j，以及该位置上孩子的糖果数j_v。
         通过这个j和j_v，就可以判断需不要补糖果，以及补几颗。
*/

This solution picks each element from the input array only once. First, we give a candy to the first child. Then for each child we have three cases:

1. His/her rating is equal to the previous one -> give 1 candy.
2. His/her rating is greater than the previous one -> give him (previous + 1) candies.
3. His/her rating is less than the previous one -> don't know what to do yet, let's just count the number of such consequent cases.

When we enter 1 or 2 condition we can check our count from 3. If it's not zero then we know that we were descending before and we have everything to update our total candies amount: number of children in descending sequence of raitings - coundDown, number of candies given at peak - prev (we don't update prev when descending). Total number of candies for "descending" children can be found through arithmetic progression formula (1+2+...+countDown). Plus we need to update our peak child if his number of candies is less then or equal to countDown.

long long minimalCandies(vector<int> &ratings) {
    int N = ratings.size();
    if (N == 0) return 0;
    long long res = 1;
    int j = -1, j_v = N+1;
    int last = 1;
    for (int i = 1; i < N; ++i)
    {
        if (ratings[i] >= ratings[i-1]) {
            last = ratings[i] == ratings[i-1] ? 1 : last + 1;
            res += last;
            j = i;
            j_v = last;
        } else {
            if (last == 1) {
                if (i - j >= j_v) {
                    res += (i - j + 1);
                    j_v++;
                } else {
                    res += i - j;
                }
            } else {
                last = 1;
                res++;
            }
        }
    }
    return res;
}
https://leetcode.com/discuss/60942/solution-time-space-explanation-possible-simplest-solution

Assuming current position is i and there are 3 cases for each i as following:

1. ratings[i - 1] < ratings[i]
2. ratings[i - 1] == ratings[i]
3. ratings[i - 1] > ratings[i]

For case 1, it's the simplest. If the previous child gets n candies, we give the i-th child n + 1candies.
For case 2, you can give any number but 0 to the i-th child and this is still compliant to the rules. But to minimize the number, you have to give the i-th child a single candy.
For case 3, it's a little bit complicated and let's discuss it by a simple example.
Given an input array [2, 3, 4, 3, 2, 1] and then we go through the process step by step.
i = 0, child[0] = 1
i = 1, child[1] = 2
i = 2, child[2] = 3
i = 3, child[3] = 1 (to minimize the number, we give the child a single candy)
i = 4, child[4] = 1

At this point, child[3] == child[4]. Therefore, we have to go back to increase child[3] by 1, i.e, child[3] = 2.

i = 5, child[5] = 1

At this point, child[4] == child[5]. We increase child[4] by 1.
However, the action affects child[2] and child[3] and we have to give them more candies.

Now let's look at the final optimal candy sequence carefully and we can see the subsequence after the third child is a reversed continuous series starting from 1.

[1 2 4 3 2 1]

Now let's reverse the subsequence and get a series starting from 1. At this point, we know we only need to count the number of lower ratings (compared to the rating of the third child) [defined as lo] and add it to the original amount of candy we gave away.

[1 2 4 1 2 3]

We record the number of candies as hi when we encounter higher or the same rating and reset loto 0.
When the number of lower ratings lo is equal to hi, we increase hi by 1.

int candy(int* ratings, int ratingsSize) { int i, sum = 1, cur = 1, lo = 0, hi = 1; if (0 >= ratingsSize || !ratings) { return 0; } for (i = 1; i < ratingsSize; ++i) { if (ratings[i] > ratings[i - 1]) { lo = 0; sum += ++cur; hi = cur; } else if (ratings[i] == ratings[i - 1]) { lo = 0; cur = 1; sum += cur; hi = cur; } else { ++lo; if (lo == hi) { hi++; sum += lo + 1; } else { sum += lo; } cur = 1; } } return sum; }
https://leetcode.com/discuss/68897/greedy-one-pass-o-n-time-o-1-space-no-multiplication-solution
Greedy: One Pass, O(n) time, O(1) space, No Multiplication Solution
public int candy(int[] ratings) { int sum = 1, x = 1, peek = 1; /*peek: number of candies the start child in the current down sequence */ boolean up = false; for (int i = 1; i < ratings.length; i++) { if (ratings[i-1] > ratings[i]) { if (!up) { sum += (x == peek - 1) ? (x = ++peek) : ++x; } else { // up to down peek = x; sum += (x = 1); } up = false; } else if (ratings[i-1] < ratings[i]) { sum += (up) ? ++x : (x = 2); up = true; } else { peek = 1; sum += (x = 1); up = false; } } return sum; }
Please also refer
http://www.cnblogs.com/TenosDoIt/p/3389479.html
这种两边扫描的方法是一种比较常用的技巧，LeetCode中Trapping Rain Water和这道题都用到了，可以把这种方法作为自己思路的一部分，通常是要求的变量跟左右元素有关系的题目会用到哈。
Hackerrank:
Alice is a kindergarden teacher. She wants to give some candies to the children in her class. All the children sit in a line and each of them has a rating score according to his or her usual performance. Alice wants to give at least 1 candy for each child.Children get jealous of their immediate neighbors, so if two children sit next to each other then the one with the higher rating must get more candies. Alice wants to save money, so she wants to minimize the total number of candies.
https://krzychusan.wordpress.com/2014/03/29/hackerrank-candies/

    for (int i=0; i<size; ++i) {

        scanf("%d", &child_rating[i]);

        candies_needed_left[i] = 1;

        candies_needed_right[i] = 1;

    }

    for (int i=1; i<size; ++i) {

        if (child_rating[i-1] < child_rating[i])

            candies_needed_left[i] = candies_needed_left[i-1] + 1;

    }

    for (int i=size-2; i>=0; --i) {

        if (child_rating[i] > child_rating[i+1])

            candies_needed_right[i] = candies_needed_right[i+1] + 1;

    }

    int total_needed_candies = 0;

    for (int i=0; i<size; ++i)

        total_needed_candies += std::max(candies_needed_left[i], candies_needed_right[i]);

http://www.cnblogs.com/TenosDoIt/p/3389479.html

算法1：该算法采用分治发，把小孩平均分左右两拨，求得两拨小孩的最小值分配方案后，还得看分界线出是否满足规则。我们用L[end]表示左边一拨小孩的右边界，R[start]表示右边一拨小孩的左边界，处理分界线出的情况分以下两种：

（1）如果L[end]等级比R[start]高，但是糖数少或相等，那么就从左边一拨小孩的右边界依次调整糖数以满足规则；

（2）如果L[end]等级比R[start]低，但是糖数多或相等，那么就从右边一拨小孩的左边界依次调整糖数以满足规则；

该算法时间复杂度为O(N*lgN)

3     int candy(vector<int> &ratings)
 4     {
 5         // Note: The Solution object is instantiated only once and is reused by each test case.
 6         int *candyNum = new int[ratings.size()];//每个小孩的糖数目
 7         memset(candyNum,0,sizeof(int)*ratings.size());
 8         int result = candyRecursive(ratings, 0, ratings.size()-1, candyNum);
 9         delete []candyNum;
10         return result;
11     }
12 
13     int candyRecursive(vector<int> &ratings, int startloc, int endloc,
14                      int candyNum[])
15     {
16         if(startloc == endloc)
17         {
18             candyNum[startloc] = 1;
19             return 1;
20         }
21         int middle = (startloc + endloc)/2;
22         int rightCandy = candyRecursive(ratings, middle+1, endloc, candyNum);
23         int leftCandy = candyRecursive(ratings, startloc, middle, candyNum);
24         if(ratings[middle+1] > ratings[middle])
25         {
26             int tmp = candyNum[middle+1] - candyNum[middle];
27             if(tmp <= 0)
28             {
29                 tmp *= -1;
30                 candyNum[middle+1] += (tmp+1);
31                 rightCandy += (tmp+1);
32                 for(int i = middle+2; i <= endloc; i++)
33                 {
34                     if(ratings[i] > ratings[i-1] && candyNum[i] <= candyNum[i-1])
35                     {
36                         int foo = candyNum[i-1] - candyNum[i] + 1;
37                         candyNum[i] += foo;
38                         rightCandy += foo;
39                     }
40                     else break;
41                 }
42             }
43         }
44         else if(ratings[middle+1] < ratings[middle])
45         {
46             int tmp = candyNum[middle+1] - candyNum[middle];
47             if(tmp >= 0)
48             {
49                 candyNum[middle] += (tmp+1);
50                 leftCandy += (tmp+1);
51                 for(int i = middle-1; i >= startloc; i--)
52                 {
53                     if(ratings[i] > ratings[i+1] && candyNum[i] <= candyNum[i+1])
54                     {
55                         int foo = (candyNum[i+1] - candyNum[i] + 1);
56                         candyNum[i] += foo;
57                         leftCandy += foo;
58                     }
59                     else break;
60                 }
61             }
62         }
63         return leftCandy + rightCandy;
64     }

X. Brute Forcehttps://leetcode.com/articles/candy/#approach-4-single-pass-approach-with-constant-space-accepted

The simplest approach makes use of a 1-d array, $candies$ to keep a track of the candies given to the students. Firstly, we give 1 candy to each student. Then, we start scanning the array from left-to-right. At every element encountered, firstly, if the current element's ratings, $ratings[i]$, is larger than the previous element($ratings[i-1]$) and $candies[i]<=candies[i-1]$, then we update $candies[i]$ as $candies[i]=candies[i-1] + 1$.Thus, now the candy distribution for these two elements $candies[i-1]$ and $candies[i]$ becomes correct for the time being(locally). In the same step, we also check if the current element's ratings, $ratings[i]$, is larger than the next element's ratings, i.e. $ratings[i]>ratings[i+1]$. If so, we again update $candies[i]=candies[i+1] + 1$. We continue this process for the whole $ratings$ array. If in any traversal, no updation of the $candies$ array occurs, it means we've reached at the final required distribution of the candies and we can stop the traversals. To keep a track of this we make use of a $flag$ which is set to $\text{True}$ if any updation occurs in a traversal.

At the end, we can sum up all the elements of the $candies$ array to obtain the required minimum number of candies.

• Time complexity : $O(n^2)$. We need to traverse the array at most $n$ times.

    public int candy(int[] ratings) {
        int[] candies = new int[ratings.length];
        Arrays.fill(candies, 1);
        boolean flag = true;
        int sum = 0;
        while (flag) {
            flag = false;
            for (int i = 0; i < ratings.length; i++) {
                if (i != ratings.length - 1 && ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {
                    candies[i] = candies[i + 1] + 1;
                    flag = true;
                }
                if (i > 0 && ratings[i] > ratings[i - 1] && candies[i] <= candies[i - 1]) {
                    candies[i] = candies[i - 1] + 1;
                    flag = true;
                }
            }
        }
        for (int candy : candies) {
            sum += candy;
        }
        return sum;
    }

http://geekscppcoding.blogspot.com/2013/10/candies-solution-hackerrank.html
O(n^2):
for (int i=0;i<N;i++)
  {
      ar1[i]=1;      
      if(i-1>=0)
      {
          if(ar[i-1]<ar[i])
            ar1[i] = ar1[i-1]+1;
          else 
          {
               int j = i;
               while(j>0 && ar[j-1] > ar[j])
               {
                ar1[j-1] = max(ar1[j-1],ar1[j] + 1);
                j= j-1;
               }          
          }
      }
  }
    int total = 0;
    for ( int i = 0; i<N ; i++){
        total += ar1[i];
    }
to-do: https://github.com/havelessbemore/hackerrank/blob/master/algorithms/dynammic_programming/candies.java
Read full article from [LeetCode] Candy | 程序员达达