akashtadwai

Profit from Stocks

Apr 9th, 2020
359
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.83 KB | None | 0 0
  1. int maxProfit(int k, vector<int>& prices) {
  2.         int n=prices.size();
  3.         //dp[i][j] -> We have i rupees in hand with j stocks.
  4.         vector< vector<int> > dp(n+1,vector<int>(k+1,-1e5));
  5.         dp[0][0]=0;
  6.         for(int i=0;i<n;i++){
  7.             for(int units=0;units<k;units++){
  8.                 dp[i+1][units]=max(dp[i+1][units],dp[i][units]); //Do nothing
  9.                 if(units>=1)
  10.                     dp[i+1][units-1]=max(dp[i+1][units-1],dp[i][units]+prices[i]); //Selling Stock
  11.                 if(units<=n-1)
  12.                     dp[i+1][units+1]=max(dp[i+1][units+1],dp[i][units]-prices[i]); //Buying Stock
  13.             }
  14.         }
  15.        /* for(int i=0;i<=n;i++) {
  16.             for(int j=0;j<=k;j++)   cout<<dp[i][j]<<" ";
  17.         cout<<endl;*/
  18.         }
  19.         return dp[n][0]; //We should leave with empty stock
Add Comment
Please, Sign In to add comment