123. Best Time to Buy and Sell Stock III
Say you have an array for which the ith 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 (ie, you must sell the stock before you buy again).
first thought is to use binary search, for each i:
- find the maximal profit between [0..i]
- find the maximal profit between [i+1..n]
- then find the maximal sum for i postion.
This approach require O(n^2)
second approach is to do it in two pass:
- first find all maximal profit between [0..i], where i reach to n. in this process, you need to keep track of the mininal buy-in price. if i sell at price[i] what is the maximal profit.
- second find all maximal profit between[n..0] i.e. from the end to the begin. if I buy-in at price[i], what will be the maximal profit,, in this process, you need to keep the maximal sell price .
Related issue
public class Solution {
public int maxProfit(int[] prices) {
int res = 0;
if(prices == null || prices.length <=1) return res;
int[] p = new int[prices.length];
int minBuyInPrice= prices[0];
p[0] = 0;
for(int i=1; i<p.length; i++){
minBuyInPrice = Math.min(prices[i], minBuyInPrice);
p[i] = Math.max(prices[i] - minBuyInPrice, p[i-1]);
}
int[] q = new int[prices.length];
q[q.length-1] = 0;
int maxSellOutPrice = prices[q.length-1];
for(int i= q.length-2; i>=0; i--){
maxSellOutPrice = Math.max(prices[i], maxSellOutPrice);
q[i] = Math.max(q[i+1], maxSellOutPrice- prices[i]);
}
for(int i=0; i<q.length; i++){
res = Math.max(res, q[i] + p[i]);
}
return res;
}
}