The Best Time to Buy and Sell Stock III problem is a classic programming problem that is often used to test a candidate's coding skills and problem-solving abilities. It is a variation of the Best Time to Buy and Sell Stock problem, with the added constraint that the individual is allowed to make at most two transactions (or buys and sells).
Here is the problem statement:
You are given an array of integers representing the price of a stock on each day. You are allowed to make at most two transactions, that is, you may buy one and sell one share of the stock multiple times. Design an algorithm to find the maximum profit.
To solve this problem, you will need to find a way to maximize the profit by making the most of the two transactions. This can be done by iterating through the prices and keeping track of the maximum profit at each point, as well as the minimum price so far. You can then use these values to calculate the maximum profit for each transaction and return the maximum of the two.
Here is an example of a solution in Python:
def maxProfit(prices):
if not prices:
return 0
# Initialize variables to track maximum profit
# and minimum price so far
max_profit = 0
min_price_so_far = float('inf')
# Iterate through prices and update max profit
# and minimum price so far
for price in prices:
min_price_so_far = min(min_price_so_far, price)
max_profit = max(max_profit, price - min_price_so_far)
# Initialize variables to track maximum profit
# and maximum price so far
max_profit_2 = 0
max_price_so_far = float('-inf')
# Iterate through prices in reverse and update
# maximum profit and maximum price so far
for price in prices[::-1]:
max_price_so_far = max(max_price_so_far, price)
max_profit_2 = max(max_profit_2, max_price_so_far - price)
# Return the maximum of the two profits
return max(max_profit, max_profit_2){codeBox}
