WINE SELLING PROBLEM

Today, we will have a walkthrough of a classical interview problem. This problem has been asked in many coding interviews and I hope you enjoy it!

Let’s begin.

Problem statement:
Given n wines in a row, with integers denoting the cost of each wine respectively. Each year you can sell the first or the last wine in the row. Let the initial profits from the wines be P1, P2, P3…Pn. In the Yth year, the profit from the ith wine will be Y*P[i]. The goal is to calculate the maximum profit that can be earned by selling all the wines.

Suppose, wine array denotes the initial cost of each wine in the first year.

wine[] = [2, 4, 6, 2, 5]

The initial thought would be to go greedy, that is, check both the ends and sell the cheaper wine every time. If we do it greedy way,

price = 2*1 = 2, remaining wines = [ 4, 6, 2, 5 ], Profit = 2
price = 4*2 = 8, remaining wines = [ 6, 2, 5 ], Profit = 10
price = 5*3 = 15, remaining wines = [ 6, 2 ], Profit = 25
price = 2*4 = 8, remaining wines = [ 6 ], Profit = 33
price = 6*5 = 30, remaining wines = [ ], Profit = 63

Therefore the overall profit received by applying a greedy approach is 63. Do you think this is the correct answer? Well, no! In a greedy approach, we select the best solution at each step. The greedy solution does not guarantee a globally optimal solution. Hence, by choosing the cheaper wine from each end every time, we might be the profit associated with the remaining unsold wines.

To the above solution, the actual optimal profit is 64. Let me show how:

wine[] = [2, 4, 6, 2, 5]

price = 2*1 = 2, remaining wines = [ 4, 6, 2, 5 ], Profit = 2
price = 5*2 = 10, remaining wines = [ 4, 6, 2 ], Profit = 12
price = 2*3 = 6, remaining wines = [ 4, 6], Profit = 18
price = 4*4 = 16, remaining wines = [ 6 ], Profit = 34
price = 6*5 = 30, remaining wines = [ ], Profit = 64

So, here we can see, in the second step, wine with price 5 is sold first instead of the wine with the price 4. By doing this, we make sure that wine with a very cheap price that is ‘2’ is sold in the third year, which otherwise would have been sold in the fourth year. Hence, increasing the overall profit.

To achieve this goal programmatically, the first approach that comes to my mind is to use recursion. In every step of recursion, we have two choices, either select the first wine or select the last wine.

Suppose we initialize the start point as 0 and endpoint as wine.length-1. Therefore, start = 0 and end = 4.
Now, we will recurse through the entire wine array and check for every possibility and will return the best possible solution.

Let’s have a look at the recursion tree.

Here, at each level, we have two choices, either to select the first wine or the last wine.

Suppose we select wine[0] first, then the profit = level*wine[0]. Here each level represents the year of selling the wine.

After selecting wine[0], we are left with wine[1..4]. We again have two choices, either select wine[1] or select wine[4]. And the same recursion will happen for the remaining wine bottles. In each recursion, we will select the subtree that will give us the maximum profit.
Let’s look at the code, here leftProfit means, profit obtained by selecting leftmost wine and rightProfit means profit obtained by selecting the rightmost wine.

int maxProfit(start, end, year)
{
   if(start==end) return wine[start]*year; //base condition
   leftProfit = wine[start]*year + maxProfit(start+1, end, year+1, wine);
   rightProfit = wine[end]*year + maxProfit(start, end-1, year+1, wine);
return max(leftProfit, rightProfit);
}

So, we have a total of 2^(n-1) choices. Therefore time complexity- O(2ⁿ).

Dynamic Programming Approach

As we can see in the recursion tree, there are many overlapping subproblems. We can reduce the time complexity by memoization technique. Let’s see how.

We will use dynamic programming to solve this problem. Create a 2D array. This array will store the maximum profit for selling the wines. Its size will be (wine.length*wine.length).

int wineProfit[wine.length][wine.length]; //assign the array with initial values of zero, it means the profit is not calculated yet.

wineProfit[0][4] = maximum profit by selling the wines from index 0 to 4. eg. [2, 4, 6, 2, 5]
wineProfit[1][3] = maximum profit by selling the wines from index 1 to 3. eg. [4, 6, 2]
and so on.

int maxProfit(start, end, year)
{
    if (start > end)
        return 0;
    else if (wineProfit[start][end] != 0)
        return wineProfit[start][end];
    else if (start <= end){
leftProfit = wine[start] * year + maxprofit(start + 1, end, year + 1);
rightProfit = wine[end] * year + maxprofit(start, end - 1, year + 1);
wineProfit[start][end] = max(leftProfit, rightProfit); //this step is memoization
return wineProfit[start][end];
    }
    else
        return 0;
}

In the DP approach, when we calculate the profit, we save it in the array so that if the profit has to be calculated again next time, we can reuse it and save time and space.

By doing memoization, the time complexity decreases to O(N²).

I hope you enjoyed this blog. Keep coding! :)