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 a row. However, the price of wines increases over time. 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*Pi. For each year, your task is to print “beg” or “end” denoting whether first or last wine should be sold. Also, calculate the maximum profit from all the wines.
Examples :
Input: Price of wines: 2 4 6 2 5
Output: beg end end beg beg
64
Explanation :
Approach: It is a standard Dynamic Programming problem. It initially looks like a greedy problem in which we should sell cheaper of wines each year but the example case (year 2) clearly proves the approach is wrong. Sometimes we need to sell an expensive wine earlier to save relatively costly wines for later years (Here, if 4 were sold in the 2nd year, in the 4th year we had to sell 2 which would be a waste of a heavy coefficient).
The second problem is to “store the strategy” to obtain the calculated price which has a fairly standard method that can be used in other problems as well. The idea is to store the optimal action for each state and use that to navigate through the optimal states starting from the initial state.
C++
// Program to calculate maximum price of wines#include <bits/stdc++.h>using namespace std;#define N 1000int dp[N][N];// This array stores the "optimal action"// for each state i, jint sell[N][N];// Function to maximize profitint maxProfitUtil(int price[], int begin, int end, int n) { if (dp[begin][end] != -1) return dp[begin][end]; int year = n - (end - begin); if (begin == end) return year * price[begin]; // x = maximum profit on selling the // wine from the front this year int x = price[begin] * year + maxProfitUtil(price, begin + 1, end, n); // y = maximum profit on selling the // wine from the end this year int y = price[end] * year + maxProfitUtil(price, begin, end - 1, n); int ans = max(x, y); dp[begin][end] = ans; if (x >= y) sell[begin][end] = 0; else sell[begin][end] = 1; return ans;}// Util Function to calculate maxProfitint maxProfit(int price[], int n) { // resetting the dp table for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) dp[i][j] = -1; int ans = maxProfitUtil(price, 0, n - 1, n); int i = 0, j = n - 1; while (i <= j) { // sell[i][j]=0 implies selling the // wine from beginning will be more // profitable in the long run if (sell[i][j] == 0) { cout << "beg "; i++; } else { cout << "end "; j--; } } cout << endl; return ans;}// Driver codeint main() { // Price array int price[] = { 2, 4, 6, 2, 5 }; int n = sizeof(price) / sizeof(price[0]); int ans = maxProfit(price, n); cout << ans << endl; return 0;} |
Java
// Program to calculate maximum price of winesimport java.io.*;class GFG { static int N = 1000; static int [][]dp = new int[N][N]; // This array stores the "optimal action" // for each state i, j static int [][]sell = new int[N][N]; // Function to maximize profit static int maxProfitUtil(int price[], int begin, int end, int n) { if (dp[begin][end] != -1) return dp[begin][end]; int year = n - (end - begin); if (begin == end) return year * price[begin]; // x = maximum profit on selling the // wine from the front this year int x = price[begin] * year + maxProfitUtil(price, begin + 1, end, n); // y = maximum profit on selling the // wine from the end this year int y = price[end] * year + maxProfitUtil(price, begin, end - 1, n); int ans = Math.max(x, y); dp[begin][end] = ans; if (x >= y) sell[begin][end] = 0; else sell[begin][end] = 1; return ans; } // Util Function to calculate maxProfit static int maxProfit(int price[], int n) { // resetting the dp table for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) dp[i][j] = -1; int ans = maxProfitUtil(price, 0, n - 1, n); int i = 0, j = n - 1; while (i <= j) { // sell[i][j]=0 implies selling // the wine from beginning will // be more profitable in the // long run if(sell[i][j] == 0){ System.out.print( "beg "); i++; } else { System.out.print( "end "); j--; } } System.out.println(); return ans; } // Driver code public static void main (String[] args) { // Price array int price[] = { 2, 4, 6, 2, 5 }; int n = price.length; int ans = maxProfit(price, n); System.out.println( ans ); }}// This code is contributed by anuj_67. |
Python3
# Python3 Program to calculate # maximum price of winesN = 1000dp = [ [-1 for col in range(N)] for row in range(N)]# This array stores the "optimal action"# for each state i, jsell = [ [0 for col in range(N)] for row in range(N)]# Function to maximize profitdef maxProfitUtil(price, begin, end, n): if (dp[begin][end] != -1): return dp[begin][end] year = n - (end - begin) if (begin == end): return year * price[begin] # x = maximum profit on selling the # wine from the front this year x = price[begin] * year + \ maxProfitUtil(price, begin + 1, end, n) # y = maximum profit on selling the # wine from the end this year y = price[end] * year + \ maxProfitUtil(price, begin, end - 1, n) ans = max(x, y) dp[begin][end] = ans if (x >= y): sell[begin][end] = 0 else: sell[begin][end] = 1 return ans# Util Function to calculate maxProfitdef maxProfit(price, n): ans = maxProfitUtil(price, 0, n - 1, n) i = 0 j = n - 1 while (i <= j): # sell[i][j]=0 implies selling the # wine from beginning will be more # profitable in the long run if (sell[i][j] == 0): print("beg", end = " ") i = i + 1 else: print("end", end = " ") j = j - 1 print(" ") return ans# Driver code# Price arrayprice = [ 2, 4, 6, 2, 5 ]size = 5ans = maxProfit(price, size);print(ans)# This code is contributed by ashutosh450 |
C#
// C# Program to calculate maximum// price of winesusing System;class GFG { static int N = 1000; static int [,]dp = new int[N, N]; // This array stores the "optimal action" // for each state i, j static int [,]sell = new int[N,N]; // Function to maximize profit static int maxProfitUtil(int []price, int begin, int end, int n) { if (dp[begin,end] != -1) return dp[begin,end]; int year = n - (end - begin); if (begin == end) return year * price[begin]; // x = maximum profit on selling the // wine from the front this year int x = price[begin] * year + maxProfitUtil(price, begin + 1, end, n); // y = maximum profit on selling the // wine from the end this year int y = price[end] * year + maxProfitUtil(price, begin, end - 1, n); int ans = Math.Max(x, y); dp[begin,end] = ans; if (x >= y) sell[begin,end] = 0; else sell[begin,end] = 1; return ans; } // Util Function to calculate maxProfit static int maxProfit(int []price, int n) { int i, j; // resetting the dp table for(i = 0; i < N; i++) for(j = 0; j < N; j++) dp[i, j] = -1; int ans = maxProfitUtil(price, 0, n - 1, n); i = 0; j = n - 1; while (i <= j) { // sell[i][j]=0 implies selling // the wine from beginning will // be more profitable in the // long run if(sell[i, j] == 0){ Console.Write( "beg "); i++; } else { Console.Write( "end "); j--; } } Console.WriteLine(); return ans; } // Driver Code public static void Main () { // Price array int []price = {2, 4, 6, 2, 5}; int n = price.Length; int ans = maxProfit(price, n); Console.WriteLine( ans ); }}// This code is contributed by anuj_67. |
Javascript
<script> // Program to calculate maximum price of wines let N = 1000; let dp = new Array(N); // This array stores the "optimal action" // for each state i, j let sell = new Array(N); for(let i = 0; i < N; i++) { dp[i] = new Array(N); sell[i] = new Array(N); for(let j = 0; j < N; j++) { dp[i][j] = 0; sell[i][j] = 0; } } // Function to maximize profit function maxProfitUtil(price, begin, end, n) { if (dp[begin][end] != -1) return dp[begin][end]; let year = n - (end - begin); if (begin == end) return year * price[begin]; // x = maximum profit on selling the // wine from the front this year let x = price[begin] * year + maxProfitUtil(price, begin + 1, end, n); // y = maximum profit on selling the // wine from the end this year let y = price[end] * year + maxProfitUtil(price, begin, end - 1, n); let ans = Math.max(x, y); dp[begin][end] = ans; if (x >= y) sell[begin][end] = 0; else sell[begin][end] = 1; return ans; } // Util Function to calculate maxProfit function maxProfit(price, n) { // resetting the dp table for (let i = 0; i < N; i++) for (let j = 0; j < N; j++) dp[i][j] = -1; let ans = maxProfitUtil(price, 0, n - 1, n); let i = 0, j = n - 1; while (i <= j) { // sell[i][j]=0 implies selling // the wine from beginning will // be more profitable in the // long run if(sell[i][j] == 0){ document.write( "beg "); i++; } else { document.write( "end "); j--; } } document.write("</br>"); return ans; } // Price array let price = [ 2, 4, 6, 2, 5 ]; let n = price.length; let ans = maxProfit(price, n); document.write( ans ); // This code is contributed by divyeshrabadiya07.</script> |
Output:
beg end end beg beg 64
Time Complexity: O(n2)
Auxiliary Space: O(n2)
Efficient approach : Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.
Steps to solve this problem :
- Create a dp to store the solution of the subproblems.
- Create another table sell to storing information when to sell.
- Initialize the dp and sell with base cases
- Now Iterate over subproblems to get the value of current problem form previous computation of subproblems stored in dp.
- Return the final solution stored in dp[0][n-1].
Implementation :
C++
#include <bits/stdc++.h>using namespace std;#define N 1000int dp[N][N]; // Dynamic programming table for storing maximum profitsint sell[N][N]; // Table for storing information about when to sellint maxProfit(int price[], int n) { // Initialize the diagonal elements of the tables for (int i = 0; i < n; i++) { dp[i][i] = n * price[i]; // If only one year is left, sell at the current price sell[i][i] = 0; // Mark as 'beg' (beginning) because only one year is left } // Calculate the maximum profit for different lengths of the subarray for (int len = 1; len < n; len++) { for (int i = 0; i < n - len; i++) { int j = i + len; int year = n - (j - i); // Calculate the current year int x = price[i] * year + dp[i + 1][j]; // Sell at the current year price and calculate the profit for remaining subarray int y = price[j] * year + dp[i][j - 1]; // Sell at the last year price and calculate the profit for remaining subarray // Choose the option that gives maximum profit if (x >= y) { dp[i][j] = x; // Maximum profit if we sell at the current price sell[i][j] = 0; // Mark as 'beg' (beginning) because we sell at the current price } else { dp[i][j] = y; // Maximum profit if we sell at the last year price sell[i][j] = 1; // Mark as 'end' because we sell at the last year price } } } // Determine the sequence of selling 'beg' and 'end' int i = 0, j = n - 1; while (i <= j) { if (sell[i][j] == 0) { cout << "beg "; i++; } else { cout << "end "; j--; } } cout << endl; return dp[0][n - 1]; // Return the maximum profit for the entire array}int main() { int price[] = {2, 4, 6, 2, 5}; int n = sizeof(price) / sizeof(price[0]); int ans = maxProfit(price, n); cout << ans << endl; return 0;} |
Output
beg end end beg beg 64
Time Complexity: O(n^2)
Auxiliary Space: O(n^2)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
