Wine Selling

Approach 1- Brute Force

After reading the explanation above, your first thought might be to use a greedy approach, that is, to check both ends and always sell the cheaper wine.

Ok, let’s try the greedy approach!

So let’s again consider the same array WinePrice: [2,4,6,2,5] 

And if proceed greedily -

As a result, the total profit obtained after selling all the wines is 63.

Well, Do you think it’s the correct answer?

To the above example, the actual profit is 64 as already explained in the problem statement. 

Why does the greedy approach fail?

In a greedy approach, we choose the best solution at each step. The greedy solution does not guarantee a globally optimal solution. As a result, by selecting the cheaper wine from each end every time, we may be able to miss the profit from the remaining unsold wines.

Now, if we pay close attention to each step, we have two options: 

choose the first wine or choose the last wine.

We can use Recursion to accomplish this goal, as we need to consider all the possibilities.

Let's examine the recursion tree below.

Source:medium

• Here each level represents the year of selling the wine.
• Suppose we selected the WinePrice[0], so the profit will be profit = level*WinePrice[0].
• After selecting WinePrice[0], we are left with WinePrice[1..4]. We again have two choices, either select WinePrice[1] or select WinePrice[4].
• The same recursion will happen for the remaining wine bottles. 
• Thus, in each recursion, we will select the subtree that will give us the maximum profit.

C++ Implementation

Output:

Complexity Analysis

Time Complexity - O(2ⁿ)

Reason: Because we either take the endpoint in the solution or do not take the endpoint, giving us two options in all cases.

Space Complexity - O(N)

The space is occupied by recursion stack and at max we we have n call in the recursion stack.

Can we optimise it further?

Yes!

The recursion tree shows that there are many overlapping subproblems.

Next, we will use the memoization technique to solve this problem because it allows us to reduce time complexity.

Let's see how things go.

Approach 2- Memoization

• Create a 2D array of size(N*N) where N is the length of the WinePrice array.
• This array will store the maximum profit for selling the wines.
• Assign the 2D array with initial values of -1, which means the profit is not calculated yet.
• The idea is to save the optimal action for each state and then use it to navigate through the optimal states beginning with the initial state.

C++ Implementation

Output:

Complexity Analysis

Time Complexity - O(N²) 

Reason: Because, using the memoization technique, when we calculate the profit, we save it in the array so that if we need to calculate it again the next time, we can reuse it and save time and space.

Space Complexity - O(N²) 

Reason: Because we created a 2D array of size(N*N) where N is the length of the WinePrice array. This array will store the maximum profit for selling the wines.

Approach 3: Dynamic Programming

• Create a 2D array of size(N*N) where N is the length of the WinePrice array.
• This array will store the maximum profit for selling the wines.
• Assign the 2D array with initial values of WinePrice.length * WinePrice[i], i.e dp[i][i] = WinePrice.length * WinePrice[i] which means if we sold the wine at the end of Yth year.
• Now start iterating from backwards i.e WinePrice.length-2 and for every index, i run an inner loop say j from i+1 to WinePrice.length.
• Why so?
  • Remember you can sell the first or last wine in a row every year.
  • So suppose you picked any wine on index i, you have the choice only to sell it in the upcoming years i.e. from i+1, you can’t go in the past years.
• The year for index i would be WinePrice.length - (j-i).
• Since we know in dynamic programming, the idea is to save the optimal action for each state and then use it to navigate through the optimal states beginning with the initial state.
• Here we have to perform three steps as follows:
  •        left = y*arr[i] + dp[i+1][j]
  •        right = y*arr[j] + dp[i][j-1]
  •        dp[i][j] = Math.max(left, right)
• Finally return dp[0][WinePrice.length-1] 

C++ Implementation

Output:

Complexity Analysis

Time Complexity - O(N²) 

Reason: Because we are using two nested loops for finding the maximum profit for selling the wines.

Space Complexity - O(N²) 

Reason: Because we created a 2D array of size(N*N) where N is the length of the WinePrice array. This array will store the maximum profit for selling the wines.

Now, if you are looking for a RoadMap to Master Dynamic Programming - Watch this video by Parikh Jain, co-founder of Coding Ninjas.

Frequently asked questions

1. What are different ways to solve the Wine Selling problem?

The Wine Selling problem can be solved using two methods-  Recursion and Dynamic Programming.

2. What are the features of dynamic programming?

The main features of dynamic programming are:

• To solve a problem optimally if it has overlapping subproblems and optimal substructure.
• To explore all the possibilities to achieve an optimal solution.
• To reduce time complexity.

3. Is math dynamic programming?

Dynamic programming is both a mathematical optimization method and a computer programming method.

4. What is the basic principle of dynamic programming?

Dynamic Programming relies on the principle of optimality. It explores all the possibilities, finds the base cases, starts with the small solutions, and then works up to reach the answer we want.

5. Is dynamic programming hard?

Dynamic programming is considered mysterious and counterintuitive among programmers, but practising many questions can make it easy for you to develop a framework for approaching dynamic programming questions. 

Key takeaways

Here we learned one of the most important and frequently asked questions in Amazon, Microsoft, and other product-based companies, i.e. Wine Selling Problem. We discussed various approaches ranging from brute force to optimal along with the C++ code for your better understanding.

Some other interesting array problems frequently encountered in interviews are Longest Palindromic Subsequence, Longest Increasing Subsequence, Minimum Jumps To Reach End, Loot Houses, Min Cost path, 0-1 Knapsackand many more.
Give it a shot yourself and try out these problems here on Coding Ninjas Studio.

Perfection comes from consistent and deliberate practice, 
So don’t stop practising and If you feel the need for expert guidance to learn more concepts, check out our DSA courses by starting your free trial today.