Best Time to Buy and Sell Stock III LeetCode Solution

Problem – Best Time to Buy and Sell Stock III LeetCode Solution

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

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

    unordered_map<string, int> memo;
    int profit(vector<int> prices, int i, int isBuy, int k){
        if(i == prices.size() || k == 2)     // return if two transactions are completed
            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){                           // if isBuy is 1, we have a choice to purchase the stock
            a = profit(prices, i + 1, 1, k);                       // do not buy
            b = profit(prices, i + 1, 0, k) - prices[i];           // buy and add the cost 
        }  
        else{                                // if isBuy is 0, we can only sell as we have already bought
            a = profit(prices, i + 1, 0, k);                       // do not sell
            b = profit(prices, i + 1, 1, k + 1) + prices[i];       // sell and add the profit
        }   
        return memo[key] = max(a, b);        // best choice among trading and skipping
    }
    
    int maxProfit(vector<int>& prices) {
        return profit(prices, 0, 1, 0);
    }

Best Time to Buy and Sell Stock III LeetCode Solution in Python

def maxProfit(self, prices):
    if not prices:
        return 0
    
    # forward traversal, profits record the max profit 
    # by the ith day, this is the first transaction
    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)
    
    # backward traversal, max_profit records the max profit
    # after the ith day, this is the second transaction 
    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

Best Time to Buy and Sell Stock III LeetCode Solution in Java

public int maxProfit(int[] prices) {
	if (prices == null || prices.length == 0) return 0;
	int lenght = prices.length;
	
	int[] leftProfit = new int[lenght];
	int leftMaxProfit = 0;
	int leftMin = prices[0];
    for (int i=0; i<lenght; i++) {
    	if (prices[i] < leftMin) leftMin = prices[i];
    	if (prices[i] - leftMin > leftMaxProfit) leftMaxProfit = prices[i]-leftMin;
    	leftProfit[i] = leftMaxProfit;
    }
    
    int maxProfit = 0;
    int rightMaxProfit = 0;
	int rightMax = prices[lenght-1];
	for (int i=lenght-1; i>=0; i--) {
    	if (prices[i] > rightMax) rightMax = prices[i];
    	if (rightMax - prices[i] > rightMaxProfit) rightMaxProfit = rightMax - prices[i];
    	int currentProfit = rightMaxProfit + (i>0 ? leftProfit[i-1] : 0);
    	if (currentProfit > maxProfit) {
    		maxProfit = currentProfit;
    	}
    }
	
    return maxProfit;
}
Best Time to Buy and Sell Stock III LeetCode Solution Review:

In our experience, we suggest you solve this Best Time to Buy and Sell Stock III LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Best Time to Buy and Sell Stock III LeetCode Solution

Find on Leetcode

Conclusion:

I hope this Best Time to Buy and Sell Stock III LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions

Leave a Reply

Your email address will not be published.