Advertisement
HjHimansh

Max Stock Profit 3 - HJ

Jul 27th, 2020
1,719
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. class Solution {
  3. public:
  4.     int maxProfit(vector<int>& prices) {
  5.       if(prices.empty())    return 0;
  6.       int minSoFar = prices[0];
  7.       vector<int> arr1(prices.size());
  8.       arr1[0] = 0;
  9.       for(int i=1; i<prices.size(); i++){
  10.         arr1[i] = max(arr1[i-1], prices[i] - minSoFar); //arr1[i] = max profit we can have by ending our transaction on day i-1, or by selling the stock on day i.. we take max of it...
  11.         minSoFar = min(minSoFar, prices[i]);
  12.       }
  13.      
  14.       int answer = 0;
  15.       int maxSoFar = prices[prices.size()-1];
  16.       for(int j=prices.size()-2; j>=0; j--){
  17.         if(j==0){
  18.             answer = max(maxSoFar-prices[j], answer);
  19.             break;
  20.         }
  21.         answer = max(maxSoFar-prices[j] + arr1[j-1], answer);
  22.         maxSoFar = max(maxSoFar, prices[j]);
  23.       }
  24.      
  25.                      
  26.       return answer;
  27.                      
  28.      
  29.     }
  30. };
Advertisement
RAW Paste Data Copied
Advertisement