Wine selling problem | Find the maximum profit from sale of wines
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 P1, P2, P3…Pn. On the Yth year, the profit from the ith wine will be 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 T test cases follow. Each test case contains two lines. The first line of each test case is a number N denoting the size of the price array of wine, the next line is N separated values of 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.
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:
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:
Time Complexity:
The time complexity for the above case is O(N^2), where N is the number of wines.
C++ Implementation:
Output
need an explanation for this answer? contact us directly to get an explanation for this answer