Prerequisite:- Dynamic Programming.
Problem :-
Given the number of days (N) for which buffalo price data is available, and the maximum number of times (K) Ramu is willing to visit the market. In each visit, Ramu can either sell a buffalo or purchase a buffalo. He has space for only one buffalo.
Calculate the maximum profit Ramu can earn by investing in buffaloes. Ramu wants to buy low and sell high, but he can only visit the market a limited number of times.
Explanation :-
Using iterative dp one can solve the problem:-
-
Create a 2D dp representing the visit(1Visit ->means you visited the market once to buy a buffalo, 2Visit ->means you visited the market twice you buy and sell a buffalo) and the day(each day represents buffalo cost in market for the given day).
-
dp[i][j] represents the maximum profit Ramu can earn if he visited the market on the jth day and made i transactions till jth day.
dp[i][j] state is dependent in dp[i][j-1] and dp[i-1][j-1]
dp[i][j]
The given dynamic programming (DP) state transition aims to calculate the maximum profit Ramu can earn by speculating on buffaloes.
The transition logic is as follows:
-
Odd Visits (Buy Operation): If the visit is odd, Ramu considers buying a buffalo. The profit for this visit is calculated by subtracting the buffalo price from the profit obtained in the previous visit (dp[i][j] = dp[i-1][j-1] - v1[j-1]). This represents the situation where Ramu buys a buffalo, reducing his profit by the purchase price.
-
Even Visits (Sell Operation): If the visit is even, Ramu considers selling a buffalo. The profit for this visit is calculated by adding the buffalo price to the profit obtained in the previous visit (dp[i][j] = dp[i-1][j-1] + v1[j-1]). This represents the situation where Ramu sells a buffalo, increasing his profit by the selling price.
-
Profit Update: During each visit, Ramu updates the maximum profit found so far (fans) by comparing it with the profit obtained for the current visit. This ensures that Ramu always tracks the maximum profit achievable at any point in time.
-
Next Day’s Profit: Additionally, the profit from the previous day’s visit is considered in both buy and sell operations. This ensures that Ramu’s decision to buy or sell a buffalo is based on the accumulated profit up to that point ).
By following this state transition logic and updating the DP table accordingly, the program efficiently computes the maximum profit Ramu can earn while adhering to the limited number of visits he can make to the market.
Solution :-
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n,m;
cin>>n>>m;
vector<long long>v1(n);
for(int i=0;i<n;i++){
cin>>v1[i];
}
vector<vector<long>>dp(m+1,vector<long>(n+1,INT_MIN));
for(int i=0;i<=n;i++){
dp[0][i] = 0;
}
long fans = 0;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(i%2==1){
dp[i][j] = dp[i-1][j-1]-v1[j-1];
}
else{
dp[i][j] = dp[i-1][j-1]+v1[j-1];
fans = max(fans,dp[i][j]);
}
dp[i][j] = max(dp[i][j],dp[i][j-1]);
}
}
cout<<fans<<"\n";
// your code goes here
}