In this post, we are going to solve the 123. Best Time to Buy and Sell Stock III problem of Leetcode. This problem 123. Best Time to Buy and Sell Stock III is a Leetcode hard level problem. Let’s see code, 123. Best Time to Buy and Sell Stock III – Leetcode Solution.

Problem

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.

Example 2 :

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.

Example 3 :

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Constraints

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 105

Now, let’s see the code of 123. Best Time to Buy and Sell Stock III – Leetcode Solution.

Best Time to Buy and Sell Stock III – Leetcode Solution

123. Best Time to Buy and Sell Stock III – Solution in Java

class Solution {
    public int maxProfit(int[] prices) {
        
        int maxProfitIfSoldToday = 0;
        int leastPrice = prices[0];
        int[] dpmpist = new int[prices.length];
        
        for(int i=1;i<prices.length;i++){
            if(prices[i] < leastPrice){
                leastPrice = prices[i];
            }
            int profit = prices[i] - leastPrice;
            if(profit > dpmpist[i-1]){
                dpmpist[i] = profit; // update
            }else{
                dpmpist[i] = dpmpist[i-1]; // no change
            }
        }
        
        int maxProfitIfBuyToday = 0;
        int maxPrice = prices[prices.length - 1];
        int[] dpmpibt = new int[prices.length];
        
        for(int i=prices.length - 2 ; i>=0 ; i--){
            if(prices[i] > maxPrice){
                maxPrice = prices[i];
            }
            
            int profit = maxPrice - prices[i];
            if(profit > dpmpibt[i+1]){
                dpmpibt[i] = profit;
            }else{
                dpmpibt[i] = dpmpibt[i+1];
            }
            
        }
        
        int max = 0;
        for(int i=0 ; i<prices.length;i++){
            if(dpmpibt[i] + dpmpist[i] > max) max = dpmpibt[i] + dpmpist[i];
        }
        
        return max;
    }
}

123. Best Time to Buy and Sell Stock III – Solution in C++

class Solution {
public:
    int maxProfit(vector<int>& prices) {
         int maxProfitIfSoldToday = 0;
        int leastPrice = prices[0];
        vector<int>dpmpist(prices.size());
        
        for(int i=1;i<prices.size();i++){
            if(prices[i] < leastPrice){
                leastPrice = prices[i];
            }
            int profit = prices[i] - leastPrice;
            if(profit > dpmpist[i-1]){
                dpmpist[i] = profit; // update
            }else{
                dpmpist[i] = dpmpist[i-1]; // no change
            }
        }
        
        int maxProfitIfBuyToday = 0;
        int maxPrice = prices[prices.size() - 1];
        vector<int>dpmpibt(prices.size());
        
        for(int i=prices.size() - 2 ; i>=0 ; i--){
            if(prices[i] > maxPrice){
                maxPrice = prices[i];
            }
            
            int profit = maxPrice - prices[i];
            if(profit > dpmpibt[i+1]){
                dpmpibt[i] = profit;
            }else{
                dpmpibt[i] = dpmpibt[i+1];
            }
            
        }
        
        int max = 0;
        for(int i=0 ; i<prices.size();i++){
            if(dpmpibt[i] + dpmpist[i] > max) max = dpmpibt[i] + dpmpist[i];
        }
        
        return max;
    }
};

123. Best Time to Buy and Sell Stock III – Solution in Python

class Solution:
	def maxProfit(self, prices: List[int]) -> int:
		s2 = 0
		s1 = 0
		b1 = -math.inf
		b2 = -math.inf

		for p in prices:
			s2 = max(s2,p+b2)
			b2 = max(b2,s1-p)
			s1 = max(s1,p+b1)
			b1 = max(b1,-p)

		return s2

Note: This problem 123. Best Time to Buy and Sell Stock III is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.