API tools faq
paste
Advertisement
Fastrail08

Best Time to Buy & Sell Stocks with atmost 2 transactions

Fastrail08
Jun 21st, 2025 (edited)
476
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.44 KB | None | 0 0
raw download clone embed print report
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. void getMaximumProfitWithTransactions(int level, int transactionState, int transactions, int currProfit, int &maxProfit, vector<int> &prices){
  5.     if(level >= prices.size()){
  6.         maxProfit = max(maxProfit, currProfit);
  7.         return;
  8.     }
  9.     //levels - stocks on each day
  10.     /*
  11.     options -
  12.     transactionState = 0; buy
  13.     transactionState = 1; sell
  14.     don't do anything
  15.     */
  16.     //only start a new transaction if transaction is closed and transactions > 0
  17.     if(transactionState == 0 && transactions > 0){
  18.         getMaximumProfitWithTransactions(level + 1, 1, transactions, currProfit - prices[level], maxProfit, prices);
  19.     }
  20.     //only call if transaction is open
  21.     if(transactionState == 1){
  22.         getMaximumProfitWithTransactions(level + 1, 0, transactions - 1, currProfit + prices[level], maxProfit, prices);
  23.     }
  24.     getMaximumProfitWithTransactions(level + 1, transactionState, transactions, currProfit, maxProfit, prices);
  25. }
  26.  
  27. int getMaximumProfitWithTransactionsMemo(int level, int transactionState, int transactions, vector<int> &prices, vector<vector<vector<int> > > &memo){
  28.     //base case
  29.     if(level >= prices.size()){
  30.         return 0;
  31.     }
  32.     //memo check
  33.     if(memo[level][transactionState][transactions] != -1){
  34.         return memo[level][transactionState][transactions];
  35.     }
  36.    
  37.     int bought = 0, sold = 0, na = 0;
  38.     //buy
  39.     if(transactionState == 0 && transactions > 0){
  40.         bought = getMaximumProfitWithTransactionsMemo(level + 1, 1, transactions, prices, memo) - prices[level];
  41.     }
  42.     if(transactionState == 1){
  43.         sold = getMaximumProfitWithTransactionsMemo(level + 1, 0, transactions - 1, prices, memo) + prices[level];
  44.     }
  45.     na = getMaximumProfitWithTransactionsMemo(level + 1, transactionState, transactions, prices, memo);
  46.     return memo[level][transactionState][transactions] = max(na, max(sold, bought));
  47. }
  48.  
  49. int main() {
  50.     // your code goes here
  51.     int n;
  52.     cin >> n;
  53.     vector<int> prices(n);
  54.     for(int i = 0; i < n; i++){
  55.         cin >> prices[i];
  56.     }
  57.     /*
  58.     Recursive call
  59.     int maxProfit = 0;
  60.     getMaximumProfitWithTransactions(0, 0, 2, 0, maxProfit, prices);
  61.     cout << maxProfit << '\n';
  62.     */
  63.     vector<vector<vector<int> > > memo(prices.size(), vector<vector<int> >(2, vector<int>(3, -1))) ;
  64.     cout << getMaximumProfitWithTransactionsMemo(0, 0, 2, prices, memo) << '\n';
  65. }
  66.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!