N people attend a gathering and will be given candies at the end.

  • Each person gets at least one candy
  • Maximum number of candies any ith person can be given, is given in an array A[ ] of length N

Success of the event is calculated by a number as follows:

initial success=0

for i=2 upto N,

success = success + absolute value of (A[i]-A[i-1])

Where A[i] is the maximum candies that can be given to i th person

Task is to find how many candies to be given to each person, to maximise the success of the gathering.

Example: If there are 6 people and the array is 3 9 9 2 2 2, the best distribution of candies is 3 1 9 1 2 1, which maximises the success value to 20

What is the algorithm to be used for this problem?

I tried the following algorithm:

  • Compare two items in the given array. Over write the smaller integer to 1. If one of the integers is already 1, no need to act and continue to next comparison.
  • If the integers are same, check making which integer as 1, gives higher contribution to the Success and decide.

Though my algorithm is working for most of the cases, it is not leading to optimal solution in the example case. It results in 1 9 1 2 1 2. Success of the result is 19, which is lesser than 20.

  • $\begingroup$ Can you please edit the question to add a reference to the original problem? $\endgroup$ – Apass.Jack Jul 21 at 9:37
  • $\begingroup$ It looks like a reference is missing still. As a rule of thumb, references should be provided so that the original work is uniquely identified and easily accessible for readers. $\endgroup$ – Apass.Jack Jul 21 at 11:27
  • $\begingroup$ Have you ever read and practiced dynamical programming? $\endgroup$ – Apass.Jack Jul 21 at 11:59
  • $\begingroup$ @Appass.Jack This is one of the questions in a coding challenge. I have given all the information I had it in the question. With regard to dynamic programming, I guess I haven't done it, not at least knowingly. $\endgroup$ – Yaksha Jul 21 at 12:09
  • $\begingroup$ Sorry, if I may appear dense about reference. 1) Credit should be attributed. 2) A reference is apt to motivate people. 3) A reference may save readers who look for related materials lots of time. 4) Many people prefer not to spoil a live coding contest/challenge. Without a reference, a question may be suspicious of plagiarism, information-holding, and contest-rule-breaking. $\endgroup$ – Apass.Jack Jul 21 at 15:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.