Instantly share code, notes, and snippets.

Embed
What would you like to do?
public class StockOne{
// example: [5, 4, 1, 2, 8, 6, 9]
public int maxProfit(int[] prices){
if(prices.length <= 1) return 0;
return maxProfitOne(prices);
// return maxProfitTwo(prices, 0, prices[0], 0);
// return maxProfitThree(prices, new Integer(-1), 0);
}
// this function use the iterative algorithm
private int maxProfitOne(int[] prices){
// in fact we don't need to use two real stacks.
// We could, but that would be just pushing and poping one elements
int currentMaxReturn = 0;
int currentLowestPrice = prices[0];
int i = 1;
int len = prices.length;
while(true){
if (i == len - 1) break; // I know this is not elegant but it helps you to understand
// the transformation from recursion to iterative form. This place
// was for the base case in recursion.
if (prices[i] <= currentLowestPrice){
// then we won't be able to make any profit
// but we should update the low price and hope it can generate a higher profit later
currentLowestPrice = prices[i];
}else{
if (prices[i] - currentLowestPrice > currentMaxReturn){
// in this case we are making a higher profit
currentMaxReturn = prices[i] - currentLowestPrice;
}else{
continue; // again, not elegant, just to show the difference between
// the recurison and its iterative form
}
}
}
if (prices[i] - currentLowestPrice > currentMaxReturn) return prices[i] - currentLowestPrice;
else return currentMaxReturn;
}
// the tail recursion form. it is so elegant but we have stackoverflow problems. so sad
// compare with the iterative algorithm above, you will see a lot of similarities.
private int maxProfitTwo(int[] prices, int maxReturn, int lowPrice, int ind){
if (ind == prices.length - 1){
// base case
if (prices[i] - lowPrice > maxReturn) return prices[i] - lowPrice;
else return maxReturn;
}
if (prices[i] <= lowPrice) return maxProfitTwo(prices, maxReturn, prices[i], ind + 1);
if (prices[i] - lowPrice > currentMaxReturn){
return maxProfitTwo(prices, prices[i] - lowPrice, lowPrice, ind + 1);
}else{
return maxProfitTwo(prices, maxReturn, lowPrice, ind + 1);
}
}
// the non-tail recursion one
private int maxProfitThree(int[] prices, Integer currentMax, int ind){
if (ind == prices.length - 1){
currentMax = prices[ind];
return 0;
}
int currentMaxReturn = maxProfitThree(prices, currentMax, ind + 1);
if (currentMax < prices[i]){
// not going to make profit, but we need to update the new currentMax
currentMax = prices[i];
return currentMaxReturn;
}else if (currentMax - prices[i] > currentMaxReturn){
return currentMax - prices[i];
}else if (currentMax - prices[i] <= currentMaxReturn){
return currentMaxReturn;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment