Candy problem on OJ
There are N children standing in a line. Each child is assigned a\n> rating value. You are giving candies to these children subjected to\n> the following requir
> There are N children standing in a line. Each child is assigned a\n> rating value. You are giving candies to these children subjected to\n> the following requirements:\n>      Each child must have at least one candy.      Children with a higher rating get more candies than their neighbors.           What is\n> the minimum candies you must give?\n\n\nI thought I got it correctly, but my code seems to fail for some test cases. The logic I was following:   \ninitialize an array of size n, called candies, with all values set to 0    \nset first value to 1    \niterate through ratings array, starting at one, and check:   \n  for element i in array rating:   \n\n 1. if rating[i] is greater than rating[i-1], set current candy nr. to\n    previous nr.+1\n 2. if rating[i] is equal to rating[i-1], set current candy nr. to the same nr. as previous\n 3. if rating[i] is less than rating[i-1], there are two possible  situations:\n\n \n - a) we can safely subtract 1 for previous candy number and still get a number that is greater than one; in that case set current candy nr.  to 1   \n - b) setting the current candy nr. to previous-1 would be less than 1; in    that case we need to backtrack; continue backtracking     while    previous rating is greater than the current && previous  candy    nr.    is less than or equal to the current; in each   iteration increase       the previous candy nr.\n\n\nI think my code now is pretty straighforward:\n\n    public int candy(int[] ratings) {\n             \n                if (ratings== null) return -1;\n                int n = ratings.length;\n                int[] candies = new int[n];\n                if (n==0) return 0;\n                candies[0] = 1;\n                int sum = 1;\n                for (int i=1; i<n; i++) {\n                    if (ratings[i] > ratings[i-1]) {\n\n                        candies[i] = candies[i-1] + 1;\n                        sum+=candies[i];\n\n                    } else if (ratings[i] == ratings[i-1]) {\n                        \n                        candies[i] = candies[i-1];\n                        sum+=candies[i];\n                    \n                   }else {\n                        if (candies[i-1]-1 >= 1) {\n                             candies[i] = 1;\n                            sum+= candies[i];\n                        } else {\n                            int k = i;\n                            candies[k]++;\n                            sum++;\n                            while (k>0 && ratings[k]<ratings[k-1] && candies[k-1]<=candies[k]) {\n                                candies[k-1]++;\n                                sum++;\n                                k--;\n                            }\n                        } \n                    }\n                }\n                return sum;\n            }\n\n[UPDATE:] Here is the failed case: [58,21,72,77,48,9,38,71,68,77,82,47,25,94,89,54,26,54,54,99,64,71,76,63,81,82,60,64,29,51,87,87,72,12,16,20,21,54,43,41,83,77,41,61,72,82,15,50,36,69,49,53,92,77,16,73,12,28,37,41,79,25,80,3,37,48,23,10,55,19,51,38,96,92,99,68,75,14,18,63,35,19,68,28,49,36,53,61,64,91,2,43,68,34,46,57,82,22,67,89]\n\nExpected: 208, I got: 210.
[]