There is a O(n) solution, which scans the ratings twice. I have detailed algorithm and kind of proof in my blog here. However, I do think it is a proof... May be we can prove the correctness by contradiction. Anyway, I describe my solution briefly as follows.
Let M[i] be the number of candies the i-th child has, M[i] is 1 at least. Additinally, it should meet two requirements:
LEFT. For i > 0, M[i] > M[i-1] if ratings[i] > ratings[i-1].
RIGHT. For i < n-1, M[i] > M[i+1] if ratings[i] > ratins[i+1].
To get the minimum sum of M, we change the two requirements as:
LEFT. For i > 0, M[i] = M[i-1] + 1 if ratings[i] > ratings[i-1].
RIGHT. For i < n-1, M[i] = M[i+1] + 1 if ratings[i] > ratins[i+1].
Then, the algorithm starts from i = 0 to n-2 for the first pass and compute M only following LEFT. Then in the second pass, starts from i = n-2 to 0 and update M following RIGHT and LEFT.
Anyone has idea to prove that the algorithm would give the correct answer? or we do not need to prove since it is naturally correct?