Problem Statement

You are given an array prices where prices[i] is the price of a given stock on the ith day.

Find the maximum profit you can achieve. You may complete at most two transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example 1:

Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.

Problem Link

Best Time to Buy and Sell Stock III - LeetCode

Reference Video

https://www.youtube.com/watch?v=wuzTpONbd-0&t=3s&ab_channel=Pepcoding

Code

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        
        int n = prices.size();
        
        int dp1[n],dp2[n];
        
        dp1[0] = 0;
        int minBuy = prices[0];
        for(int i=1;i<n;i++) 
        {
            // storing minimum price of stock from 0 to ith day (including ith day)
            minBuy = min(minBuy,prices[i]);
            // storing the maximum profit if stock buy and sell happens between 0 to ith day (both inclusive)
            dp1[i] = max(dp1[i-1],prices[i]-minBuy);
        //  dp1[i] = max(previous profit, profit gained if it was mandatory to sell on day i)  
            
        }
        dp2[n-1] = 0;
        int maxSell = prices[n-1];
        
        for(int i=n-2;i>=0;i--)
        {
            // storing maximum price of stock from i to (n-1)th day (including (n-1)th day)
            maxSell = max(maxSell,prices[i]);
            // storing the maximum profit if stock buy and sell happens between i to (n-1)th day (both inclusive)
            dp2[i] = max(dp2[i+1],maxSell-prices[i]);
         // dp2[i] = max(previous profit, profit gained if it was mandatory to buy on day i)
        }
        
        int res = 0;
        
        for(int i=0;i<n;i++)
            res = max(res,dp1[i]+dp2[i]);
        
        return res;
    }
};
// Time Complexity : O(n)
// Space Complexity : O(n)