Selling Wine || DP || EASY || C++
Vidhu
6934
Interview

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.

Input: Price of wines: 2 4 6 2 5
Output: beg end end beg beg 
         64

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 = 1*2 = 2, remaining wines = [ 4, 6, 2, 5 ], Profit = 2
price = 2*4 = 8, remaining wines = [ 6, 2, 5 ], Profit = 10
price = 3*5 = 15, remaining wines = [ 6, 2 ], Profit = 25
price = 4*2 = 8, remaining wines = [ 6 ], Profit = 33
price = 5*6 = 30, remaining wines = [ ], Profit = 63

This is wrong since the output is 64
Correct :

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

So we need to consider all the possibilities and that's where recursion comes into action !

Recusive Code

int solve(int price[], int i, int j, int year)
{
    if(i>j) return 0;
    if(i==j) return price[i]*year;
    
    int left = price[i]*year + solve(price,i+1,j,year+1);
    int right = price[j]*year +solve(price,i,j-1,year+1);
    return max(left,right);
}
int maxProfit(int price[], int n)
{
    return solve(price,0,n-1,1);
}

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

  • Above code has many repeating subproblems. Let’s have a look at the recursion tree.
    image
    Let;s memoize it

Memoization

int dp[100][100];
int solve(int price[], int i, int j, int year)
{
    if(i>j) return 0;
    if(i==j) return price[i]*year;
    
    if(dp[i][j]!=-1) return dp[i][j];
    int left = price[i]*year + solve(price,i+1,j,year+1);
    int right = price[j]*year +solve(price,i,j-1,year+1);
    return dp[i][j] = max(left,right);
}
int maxProfit(int price[], int n)
{
    memset(dp,-1,sizeof(dp));
    return solve(price,0,n-1,1);
}

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

Comments (12)