Maximum Profit given n apples to sell

Question

Given n apples to sell and an array of n integers 'price' such that price[i] denotes the price at which i+1 apples can be sold.Compute the maximum revenue that we can generate from selling n apples in any combination we may choose.

Example: Given 8 apples and the price array as follows:-

{1,5,8,9,10,17,17,20}
i.e.price of 1 apple = $1
total selling price of 2 apples = $5, etc.

The maximum revenue would be generated by selling 2 + 6 apples for a total of 5 + 17 = $22.

I have a simple recursive solution in mind but am wondering what is the best time complexity that we can achieve? Is there scope to apply Dynamic Programming or Memoization?

Thanks!

Answer 1

Definitions

Let dp[k] denotes the profit for selling k apples in the optimal way

Let profit[k] detones the profit for selling k apples at once.

Recurrence relation

Clearly, dp[0] = 0.

Then we can define, a recurrence relation as follows:

dp[k] = max{dp[i] + profit[k - i]}, where 0 <= i < k

You are interested in computing dp[n].

Conclusion

You can easily implement it using bottom-up approach or memoization and both method are pretty straighforward.

The time complexity of this solution is O(n^2), because computing a single entry in dp array takes O(n) time.

Answer 2

Is there scope to apply Dynamic Programming or Memoization?

Yes, your problem is similar to the Rod-Cutting problem, which is a famous example of dynamic programming.

I have a simple recursive solution in mind but am wondering what is the best time complexity that we can achieve?

The time complexity for the naïve apprach isO(2^n) while O(n²) using dynamic programming.

Answer 3

Yes, it is pretty similar to the rod-cutting problem.So, the DP solution is
P[i]=MAX(S_i, k=1..i MAX(P[k]+P[i-k]))
Max i=1 to n P[i] gives you the answer.
S_i= price of i apples from the given array.
Running time: O(n)
Couldn't comment on previous comments yet since it requires level 50 and i have just joined.