Wine and Maximum Price Problem

Problem statement

Imagine you have a collection of N wines placed next to each other on a shelf. For simplicity, let us number the wines from left to right as they are standing on the shelf with integers from 1 to N, respectively. The price of the $i^{th}$ wine is $p_{i}$ (prices of different wines can be different). Because the wines get better every year, supposing today is the year 1, on year y the price of the $i^{th}$ wine will be y*pi, i.e., y-times the value of that current year.

You want to sell all the wines you have, but you want to sell exactly one wine per year, starting this year. One more constraint is that each year you are allowed to sell only either the leftmost or the rightmost wine on the shelf and you are not allowed to reorder the wines on the shelf (i.e., they must stay in the same order as they were in the beginning).

You want to find the maximum profit you can get if you sell the wines in optimal order.

For example, suppose that the prices of the wines are the following (in the order as they are placed on the shelf, from left to right):

p1 = 1, p2 = 4, p3 = 2, p4 = 3

The optimal solution would be to sell the wines in the order p1, p4, p3, p2 for a total profit 1 * 1 + 3 * 2 + 2 * 3 + 4 * 4 = 29.

Now let’s take a look at why this is not a Greedy problem. If we were assuming this to be a greedy problem, we could sell the cheaper wine from the two (leftmost and rightmost) available wines every year.

Let the prices of 4 wines be: 2, 3, 5, 1, 4.

• At year = 1: {2,3,5,1,4} sell p1 = 2 to get cost = 2
• At year = 2: {3,5,1,4} sell p2 = 3 to get cost = 2 + 2*3 = 8
• At year = 3: {5,1,4} sell p5 = 4 to get cost = 8 + 4*3 = 20
• At year = 4: {5,1} sell p4 = 1 to get cost = 20 + 1*4 = 24
• At year = 5: {5} sell p3 = 5 to get cost = 24 + 5*5 = 49

The Greedy approach gives an optimal answer of 49, but if we sell in the order of p1, p5, p4, p2, p3 for a total profit 2 * 1 + 4 * 2 + 1 * 3 + 3 * 4 + 5 * 5 = 50, it would mean that the Greedy approach fails.

Think of a possible solution before moving forward.

Solution: Recursive approach

Let us first define the recurrence relation for this problem.

answer = max{price[ start] * year + maxPrice(price, start+1, end, year + 1), price[end] * year + maxPrice(price, start, end - 1,year + 1)}

Let’s see how that works in the code.

For each endpoint at every function call, we either take this endpoint in the solution, increment/decrement the endpoint index, or we do not take this endpoint in the solution.

We are doing this for each and every n endpoint (n is the number of wines on the table). So, T = O($2^{n}$), which is exponential time complexity.

Let’s see the code now.