# Minimum give away on performance based queue?

I'm trying to solve algorithm problem, so far no luck

Lets imagine A is an employer and there are N employee currently on line (queuing) for receiving their paycheck of the month, and each of the employee are given the same base salary, \$1000 each, but their bonuses are based on their performance and where they are right now on queue line. As employer, A want to minimize the bonus for whole employees, so the company can save money.

So if the input is an array of employee and their performance metric, where index 0 is first on queue, and so on.

The employer want to see the output that indicate on how much each employee will receive as bonuses, and the bonuses are calculated with following rules:

• Bonuses given are the minimum possible payout to employee, with the restrictions below.
• An employee can receive no bonuses at all, i.e: USD0
• Bonuses are in the multiple of USD100, i.e: USD0, USD100, USD200, USD300, so on
• Between any two employee that are next to each other in queue line the bonus must reflect their performance, i.e: the higher of the two s receive higher bonus, and vice versa.
• Two employee that are next to each other in queue line can have same bonuses/not receiving bonuses if they have the same performance metric.

So, for example, if the input is [9,7,1,2,1,1,7,4,6,1,7,8,6,2,2,1,1] and the value of employee performance metric was restricted to >=1 and <=10.

We could expect the output be like [200,100,0,100,0,0,100,0,100,0,100,300,200,100,100,0,0]

Here other input and output example:

    input = [9,8,7,6,5,4,3,2,1,7,8,9,1,1,1]
output = [800,700,600,500,400,300,200,100,0,100,200,300,0,0,0]

input = [3,5,4,7,8,6,4,4,5,7,7,6,2,2,2,3,4]
output = [0,100,0,300,200,100,0,0,100,200,200,100,0,0,0,100,200]


Thanks.

• Is the employer allowed to change the order in the queue, or only the amount given to the employees for a given order? If the latter, wouldn't simply finding local minima and putting 0 there work? – Discrete lizard Jan 2 '18 at 15:07
• no, the queue, i.e: input array, is fixed – xcode Jan 2 '18 at 15:08
• What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises and contest-style problems for you is unlikely to achieve that. You might find this page helpful in improving your question. – D.W. Jan 2 '18 at 16:09
• What algorithm design paradigms have you already tried, and where did you get stuck? Have you tried a greedy algorithm? Have you tried dynamic programming? You might refer to our guide on how to build dynamic programming algorithms for tips on how to get started: cs.stackexchange.com/tags/dynamic-programming/info. – D.W. Jan 2 '18 at 16:10
• I don't know what paradigm, i'm beginner, but the last method that I tried is, first find the smallest metric and replace it with 0, and work from there to right and left of the 0, increasing it by 100 if they have greater metric than previous one if not then just don't do anything, that's it it could still leave many array element 'untreated' and if there is this sequence 1,4,3,2,1 my algorithm still treat it to become 0,100,200,100,0 instead of 0,300,200,100,0 – xcode Jan 3 '18 at 5:30