Say you have an array for which the i-th element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again)
we can use two arraysf[i] and b[i] to record the maximum profit for price[0...i−1] and price[i...n−1] , respectively. After that, we just need to find the maximum of f[i]+b[i]
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again)
we can use two arrays
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0)
return 0;
// forward[i]: maximum profit for prices[0...i-1]; forward[0]=0
int[] forward = new int[prices.length+1];
int lowestBuyInPrice = prices[0]; // Lowest buy-in price up to now
for (int i = 2; i <= prices.length; i++) { // Traverse forwards
forward[i] = Math.max(forward[i-1], prices[i-1]-lowestBuyInPrice);
lowestBuyInPrice = Math.min(lowestBuyInPrice, prices[i-1]);
}
// backward[i]: maximum profit for prices[i...n-1]
int[] backward = new int[prices.length];
int highestSellOutPrice = prices[prices.length-1]; // Lowest buy-in price up to now
for (int i = prices.length-2; i >= 0; i--) { // Traverse backwards
backward[i] = Math.max(backward[i+1], highestSellOutPrice-prices[i]);
highestSellOutPrice = Math.max(highestSellOutPrice, prices[i]);
}
// Find the maximum of forward[i]+backward[i]
int maximumProfit = 0;
for (int i = 0; i < prices.length; i++) {
maximumProfit = Math.max(maximumProfit, forward[i]+backward[i]);
}
return maximumProfit;
}
Read full article from LeetCode - Best Time to Buy and Sell Stock III | Darren's Blog
No comments:
Post a Comment