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

Best Time to Buy and Sell Stock III
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;
}

Best Time to Buy and Sell Stock III