Here, We see Best Time to Buy and Sell Stock III LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Best Time to Buy and Sell Stock III LeetCode Solution

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.

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.

Best Time to Buy and Sell Stock III LeetCode Solution C++

class Solution {
public:
    unordered_map<string, int> memo;
    int profit(vector<int> prices, int i, int isBuy, int k){
        if(i == prices.size() || k == 2)
            return 0;
        string key = to_string(i) + "-" + to_string(isBuy) + "-" + to_string(k);
        if(memo.find(key)!=memo.end())
            return memo[key];
        int a,b;
        if(isBuy){
            a = profit(prices, i + 1, 1, k);
            b = profit(prices, i + 1, 0, k) - prices[i];
        }  
        else{
            a = profit(prices, i + 1, 0, k);
            b = profit(prices, i + 1, 1, k + 1) + prices[i];
        }   
        return memo[key] = max(a, b);
    }
    
    int maxProfit(vector<int>& prices) {
        return profit(prices, 0, 1, 0);
    }
};Code language: PHP (php)

Best Time to Buy and Sell Stock III LeetCode Solution Java

class Solution {
public int maxProfit(int[] prices) {
		int sell1 = 0, sell2 = 0, buy1 = Integer.MIN_VALUE, buy2 = Integer.MIN_VALUE;
		for (int i = 0; i < prices.length; i++) {
			buy1 = Math.max(buy1, -prices[i]);
			sell1 = Math.max(sell1, buy1 + prices[i]);
			buy2 = Math.max(buy2, sell1 - prices[i]);
			sell2 = Math.max(sell2, buy2 + prices[i]);
		}
		return sell2;
	}
}Code language: JavaScript (javascript)

Best Time to Buy and Sell Stock III LeetCode Solution JavaScript

var maxProfit = function(prices) {
  if(prices.length == 0) return 0
  let dp = new Array(prices.length).fill(0);
  let min = prices[0];
  let max = 0;
  for (let i = 1; i < prices.length; i++) {
    min = Math.min(min, prices[i]);
    max = Math.max(max, prices[i] - min);
    dp[i] = max;
  }
  min = prices[0];
  max = 0;
  for (let i = 1; i < prices.length; i++) {
    min = Math.min(min, prices[i] - dp[i]);
    max = Math.max(max, prices[i] - min);
    dp[i] = max;
  }
  return dp.pop();
};Code language: JavaScript (javascript)

Best Time to Buy and Sell Stock III LeetCode Solution Python

class Solution(object):
    def maxProfit(self, prices):
        if not prices:
            return 0
        profits = []
        max_profit = 0
        current_min = prices[0]
        for price in prices:
            current_min = min(current_min, price)
            max_profit = max(max_profit, price - current_min)
            profits.append(max_profit)
        total_max = 0    
        max_profit = 0
        current_max = prices[-1]
        for i in range(len(prices) - 1, -1, -1):
            current_max = max(current_max, prices[i])
            max_profit = max(max_profit, current_max - prices[i])
            total_max = max(total_max, max_profit + profits[i])
        return total_max