Solution to LeetCode problem Best Time to Buy and Sell Stock III.
This is quite similar to the Codility Max-Double-Slice Sum problem.
We compute M1[i] – the maximal profit possible considering all the prices up to index \(i\), and similarly, M2[i] – the max profit considering all the prices from prices[i..N-1]. The simply iterate through every index \(i\), and find the maximum of M1[i] + M2[i]. This takes all the required cases into consideration.
public int maxProfit(int[] prices) {
int N = prices.length;
if(N == 0) return 0;
int[] M1 = new int[N];
int[] M2 = new int[N];
int minPrice = prices[0];
for(int i = 1; i < N; i++){
minPrice = Math.min(minPrice, prices[i]);
M1[i] = Math.max(M1[i-1], prices[i]-minPrice);
}
int maxPrice = prices[N-1];
for(int i = N-2; i >= 0; i--){
maxPrice = Math.max(maxPrice, prices[i]);
M2[i] = Math.max(M2[i+1], maxPrice-prices[i]);
}
int best = 0;
for(int i = 0; i < N; i++){
best = Math.max(best, M1[i]+M2[i]);
}
return best;
} Here is a version with a little more expansion so that it’s easier to see what’s going on.
public int maxProfit(int[] prices) {
int N = prices.length;
if(N == 0) return 0;
int[] M1 = new int[N];
int[] M2 = new int[N];
// No profit at the very beginning
M1[0] = 0;
M2[N-1] = 0;
int minPrice = prices[0];
int maxProfit1 = 0;
for(int i = 1; i < N; i++){
minPrice = Math.min(minPrice, prices[i]);
maxProfit1 = Math.max(maxProfit1, prices[i]-minPrice);
M1[i] = maxProfit1;
}
int maxPrice = prices[N-1];
int maxProfit2 = 0;
for(int i = N-2; i >= 0; i--){
maxPrice = Math.max(maxPrice, prices[i]);
maxProfit2 = Math.max(maxProfit2, maxPrice-prices[i]);
M2[i] = maxProfit2;
}
int best = 0;
for(int i = 0; i < N; i++){
best = Math.max(best, M1[i]+M2[i]);
}
return best;
}