We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

what i did was first create a list of troughs in the rankings array (a trough is an item which is less than or equal to both its right and left neighbors) , then for each trought i do the following :

set the number of candies at the trough to 1.

go right incrementing the number of candies by one each time until i find a ranking crest.

repeat step 2 but to the left.

its not exactly dynamic programming , but its O(N) time complexity.

but i am wandering whats the dynamic programming version of the solution.

To figure out the candies a child gets, is an equation involving the number of candies its neightbours get and this equation depends on their relative ranking. DP version is to calulate the candies count of neighbours if it hasn't been done so far and storing it and reusing again later while calculating candy count of another child. In your code, you are calculating 'c' array multiple times which you shouldn't be doing. Calculate the value once and save it.

## Candies

You are viewing a single comment's thread. Return to all comments →

what i did was first create a list of troughs in the rankings array (a trough is an item which is less than or equal to both its right and left neighbors) , then for each trought i do the following :

set the number of candies at the trough to 1.

go right incrementing the number of candies by one each time until i find a ranking crest.

repeat step 2 but to the left.

its not exactly dynamic programming , but its O(N) time complexity.

but i am wandering whats the dynamic programming version of the solution.

To figure out the candies a child gets, is an equation involving the number of candies its neightbours get and this equation depends on their relative ranking. DP version is to calulate the candies count of neighbours if it hasn't been done so far and storing it and reusing again later while calculating candy count of another child. In your code, you are calculating 'c' array multiple times which you shouldn't be doing. Calculate the value once and save it.