Home » Interview coding problems/challenges

# Wine selling problem | Find the maximum profit from sale of wines

**Wine selling problem**: Here, we are going to learn how to solve the wine solving problem, **how to find the maximum profit from the sale of wines?** This is a very popular coding problem that has been featured in interview rounds of many big companies such as Goldman Sachs, Amazon, Tower Research and others.

Submitted by Divyansh Jaipuriyar, on April 21, 2020

**Problem statement:**

Given * n* wines in a row, with integers denoting the cost of each wine respectively. Each year you can sale the first or the last wine in the row. Let the initial profits from the wines be

*. On the*

**P1, P2, P3…Pn***year, the profit from the ith wine will be*

**Y**^{th}*,*

**Y*P[i]****calculate the maximum profit from all the wines**.

**Input:**

The first line of the input is * T* denoting the number of test cases. Then

*test cases follow. Each test case contains two lines. The first line of each test case is a number*

**T***denoting the size of the price array of wine, the next line is*

**N***separated values of*

**N***.*

**P[]****Output:**

For each test case output in a new line the max profit from the sale of all the wines.

**Example with explanation:**

Input: T = 1 // Test case N = 4 P = [1,4,2,3] Output: 29 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. Input: T = 1 // Test case N = 5 P = [2,3,5,1,4] Output: 50 The optimal solution would be to sell the wines in the order p1, p5, p4, p2, p3 for a total profit 2 * 1 + 4 * 2 + 1 * 3 + 3 * 4 + 5 * 5 = 50.

**Solution Approach**

**1) Recursive Approach**

Here we will try all possible solution(using all subproblems answer) then check the solution which gives the maximum answer. We will pick either the first wine and multiply with the current year and recursively move to next year or we will select the last wine and multiply with the current year and move recursively to the next part then we will select the maximum of the two subproblems for the current solution.

**Pseudo Code:**

int maxprofit(start, end, year) { if (start > end) return 0; if (start <= end) return max(P[start] * year + maxprofit(st + 1, end, year + 1), P[end] * year + maxprofit(st, end - 1, year + 1)); else return 0; }

**Time Complexity:**

The time complexity for the above approach is **O(2^n)**, exponential time since we either take endpoint in the solution or we do not take the endpoint,that is we have two options for all the cases.

**C++ Implementation:**

#include <bits/stdc++.h> using namespace std; int maxprofit(int P[], int start, int end, int n, int year) { if (start > end) return 0; else if (start <= end) { return max(P[start] * year + maxprofit(P, start + 1, end, n, year + 1), P[end] * year + maxprofit(P, start, end - 1, n, year + 1)); } else return 0; } int main() { int t; cout << "Enter number of test cases: "; cin >> t; while (t--) { int n; cout << "Enter number of wines: "; cin >> n; int P[n]; cout << "Enter the wines prices: "; for (int i = 0; i < n; i++) cin >> P[i]; int start = 0; int end = n - 1; int year = 1; int res = maxprofit(P, start, end, n, year); cout << "Max Profit: "; cout << res << "\n"; } return 0; }

**Output**

Enter number of test cases: 2 Enter number of wines: 4 Enter the wines prices: 1 4 2 3 Max Profit: 29 Enter number of wines: 5 Enter the wines prices: 2 3 5 1 4 Max Profit: 50

**2) Dynamic Programming (Better Approach):**

By carefully observing the recursion tree, we can see that we encounter the property of subproblem overlapping which can be prevented using memoization or dynamic programming.

We will use the 2-D array to store the profit for a particular year, initially, all the profit from the sale is zero. For memoization, we will use the start and end state. If the dp[start][end] is equal to zero it means we haven't solved for that year and if the dp[start][end] is not equal to zero then that dp[start][end] is returned.

**Pseudo Code:**

int maxprofit(start, end, year) { if (start > end) return 0; if (dp[start][end] != 0) return dp[start][end]; else if (start <= end) return dp[start][end] = max(P[start] * ye + maxprofit(start + 1, end, year + 1), P[end] * year + maxprofit(start, end - 1, year + 1)); else return 0; }

**Time Complexity:**

The time complexity for the above case is **O(N^2)**, where * N* is the number of wines.

**C++ Implementation:**

#include <bits/stdc++.h> using namespace std; int dp[1004][1004]; int maxprofit(int P[], int start, int end, int n, int year) { if (start > end) return 0; else if (dp[start][end] != 0) return dp[start][end]; else { dp[start][end] = max(P[start] * year + maxprofit(P, start + 1, end, n, year + 1), P[end] * year + maxprofit(P, start, end - 1, n, year + 1)); return dp[start][end]; } } int main() { int t; cout << "Enter number of test cases: "; cin >> t; while (t--) { int n; cout << "Enter number of wines: "; cin >> n; int P[n]; cout << "Enter the wines prices: "; for (int i = 0; i < n; i++) cin >> P[i]; for (int i = 0; i <= n; i++) for (int j = 0; j <= n; j++) dp[i][j] = 0; int start = 0; int end = n - 1; int year = 1; int res = maxprofit(P, start, end, n, year); cout << "Max Profit: "; cout << res << "\n"; } return 0; }

**Output**

Enter number of test cases: 2 Enter number of wines: 6 Enter the wines prices: 2 5 6 2 4 5 Max Profit: 93 Enter number of wines: 5 Enter the wines prices: 2 3 5 1 4 Max Profit: 50

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.