Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- int maxProfit(int k, vector<int>& prices) {
- int n=prices.size();
- //dp[i][j] -> We have i rupees in hand with j stocks.
- vector< vector<int> > dp(n+1,vector<int>(k+1,-1e5));
- dp[0][0]=0;
- for(int i=0;i<n;i++){
- for(int units=0;units<k;units++){
- dp[i+1][units]=max(dp[i+1][units],dp[i][units]); //Do nothing
- if(units>=1)
- dp[i+1][units-1]=max(dp[i+1][units-1],dp[i][units]+prices[i]); //Selling Stock
- if(units<=n-1)
- dp[i+1][units+1]=max(dp[i+1][units+1],dp[i][units]-prices[i]); //Buying Stock
- }
- }
- /* for(int i=0;i<=n;i++) {
- for(int j=0;j<=k;j++) cout<<dp[i][j]<<" ";
- cout<<endl;*/
- }
- return dp[n][0]; //We should leave with empty stock
Add Comment
Please, Sign In to add comment