StockOne.java

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