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:
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.