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