YEZAELP

LeetCode: Best Time to Buy and Sell Stock III

Nov 17th, 2021 (edited)
251
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     const int inf = 1e9;
  4.    
  5.     int dp[100010][5];
  6.     int mx[100010][5];
  7.    
  8.     int maxProfit(vector<int>& prices) {
  9.         int n = prices.size();
  10.         for(int i=n-1;i>=0;i--){
  11.             dp[i][1] = max(dp[i+1][1], - prices[i] + mx[i+1][0]);
  12.             dp[i][2] = max(dp[i+1][2], - prices[i] + mx[i+1][1]);
  13.             mx[i][0] = max(mx[i+1][0], prices[i] + dp[i+1][0]);
  14.             mx[i][1] = max(mx[i+1][1], prices[i] + dp[i+1][1]);
  15.         }
  16.  
  17.         return max(dp[0][1], dp[0][2]);
  18.     }
  19. };
RAW Paste Data Copied