I solved it, but I have no idea how to prove my solution is correct. First I go left to right and set "next" candy value to either "previous+1" or "1". This way I get the up trends. Then I go right to left and do the same, this way getting the down trends. Very simple O(2xN) solution, but doesn't look like it's the intended one.

What kind of class in the world would have 100000 kids.... LOL

I don't see why this is listed under dynamic programming.

Here is the way I approached this problem.

Let S[i] = The length of decreasing sequence that begins with the i-th element of the given ratings array. If there is no decreasing sequence beginning at i, S[i] = 1 by default.

Let C[i] = the minimum no. of candies given to the i-th student. The ultimate solution we want is sum(C[i]) for all i.

Key insight: C[i] = S[i] for all i, EXCEPT when ratings[i] > ratings[i-1], in which case C[i] = max(S[i], C[i-1]+1).

As an example, consider a ratings array like [4, 4, 2, 3, 4, 1]. The corresponding S array would be: S = [1, 2, 1, 1, 2, 1] The corresponding C array is: C = [1, 2, 1, 2, 3, 1] Solution: sum(C) = 10.

(Also note that it is not necessary to compute S[i] from scratch for every i. If S[i-1] > 1, then S[i] = S[i-1] - 1. This improves efficiency.)

I used DP. The right to left and left to right solution works. But it is a lot fun if you use DP.

1. Every student's candy value depends on their left and right student.
2. So build the solution by calculating the neighbours value and then reccursing back to the top using:

func getMaxFromRight(int idx):
//Handle base case and edge cases here
 if ranking[idx-1] < ranking[idx] > ranking[idx+1];
 	then candy[idx] = max(candy[idx-1], getMaxFromRight(idx+1))+1;
 else if (ranking[idx+1] < ranking[idx])
     then candy[idx] = getMaxFromRight(idx+1)+1;
 else if (ranking[idx-1] < ranking[idx])
     then candy[idx] =  candy[idx-1]+1;
          getMaxFromRight(idx+1)+1;
 else
     candy[idx] = 1;
     getMaxFromRight(idx+1)+1;

return candy[idx]

Note: You have to handle base case for return and also edge cases of idx-1 >=0 and idx+1 < candy.length