304 North Cardinal St.
Dorchester Center, MA 02124

# 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
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])

``````

## 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;
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