(The ‘candies’ questions in the Hackerrank interview preparation section.)
Consider the following exercise:-
This was listed under dynamic programming exercises but my solution uses a slightly different approach. It is true that one needs to keep track of elements already parsed.
First I tried a natural
O(N^2) solution that went back and corrected itself every time the current score was lower than the previous one.
This passed all of the tests except for one which failed with a
timeout type error.
However going back to correct the previous entries is not necessary.
Instead one can keep track of where one started going down and then fill in everything at once when one knows when to stop going down.
A rough implementation of this idea:
which did pass all the tests.