1
$\begingroup$

Suppose there exists a list of unsorted int numbers [91,89,90,90,90,89,91].

I need to maximize the profit by selecting an element, in as many steps as needed, which satisfies the condition that, when element(i) is chosen, the profit would be value of element(i) multiplied by its frequency/occurrence in list, an extra condition is that element(i), element(i)-1 and element(i)+1 should be removed as well.

So for the given array [91,89,90,90,90,89,91], if I choose 90 and remove it, my profit will be 90*3=270 and my array reduces to [], because I remove (90-1) and (90+1) in the same step.

However, if I had chosen, 89 then profit would be 89*2 and upon removing 89 and 89+1(There is no element corresponding to (89-1)), I am left with [91,91]. In the next step, I remove 91, this results in a total profit of 89*2+91*2. The profit is greater than the one obtained after selecting 90.

Another example is list [3,4,2], suppose I select 3, this means profit is 3*1 and I remove 3, 2 and 4 which results in empty list and profit is 3. Now, I choose 2, this results in removal of 2 and 3, profit will be 2*1. List will be [4]. Next step profit will be 4*1, so total profit will be 2+4=6.
I tried to select max element in array and remove it, but it will not work for list [1,1,1,1,1,1,1,1,1,2]. Here, 1 needs to be selected, instead of 2. Because selecting 2, would result in a profit of 1 versus selecting 1 which would give 1*9.

What approach would be ideal to solve this? Please provide your opinions. Thank you

$\endgroup$
2
$\begingroup$

This is a special case of maximum weighted independent set on an interval graph. Another way to phrase your problem is as follows: choose a subset of your neighbors of maximal sum in which no two elements have difference exactly 1.

One simple way to solve your problem is using dynamic programming. First sort the list, and remove duplicates (but remember how many of each number appear in the original list). Now use dynamic programming to calculate the optimal solution for every prefix of the sorted list.

$\endgroup$
  • $\begingroup$ If I may ask, would you be kind enough to provide an implementation of this, since I am still learning the concept of dynamic programming. $\endgroup$ – Ashwin V Oct 8 '17 at 17:00
  • 1
    $\begingroup$ On this site we concentrate on describing algorithms, leaving their implementation to programmers. Implementing this particular algorithm will greatly contribute to your understanding of dynamic programming. The first step would be to come up with complete pseudocode, which is missing from my answer on purpose. $\endgroup$ – Yuval Filmus Oct 8 '17 at 17:08

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.