Best Time to Sell and Buy Stocks

BestTimetoSellandBuyStocks.java

/**
 * Say you have an array for which the ith element is the price of a given stock on day i.
 * 
 * If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
 */
 
public class Solution{
    public int maxProfit(int[] prices) {
        if(prices.length == 0 || prices.length == 1) return 0;
        int max_profit = 0;
        int buy_date = 0;
        for(int i = 0; i < prices.length; i++){
            if(prices[i] < prices[buy_date]) buy_date = i;
            int tmp_profit = prices[i] - prices[buy_date];
            if(tmp_profit > max_profit) max_profit = tmp_profit;   
        }
        return max_profit;
    }
}

BestTimetoSellandBuyStocksII.java

/**
 * Say you have an array for which the ith element is the price of a given stock on day i.
 * Design an algorithm to find the maximum profit. 
 * You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). 
 * However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
 */

public class Solution{
    public int maxProfit(int[] prices) {
        if(prices.length < 2) 
            return 0;
        int max = 0;
        for(int i = 1; i < prices.length; i++){
            int tmp_profit = prices[i] - prices[i-1];
            if(tmp_profit > 0)
                max += tmp_profit;
        }
        return max;
    }
}

BestTimetoSellandBuyStocksIII.java

/**
 * Say you have an array for which the ith element is the price of a given stock on day i.
 * Design an algorithm to find the maximum profit. You may complete at most two transactions.
 * You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
 */
 
public class Solution{
    public int maxProfit(int[] prices) {
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        int[] forward = new int[prices.length];
        int[] backward = new int[prices.length];
        for(int i = 0; i < prices.length; i++){
            // the first transaction profit
            if(prices[i] > min)
                forward[i] = Math.max(prices[i] - min, forward[i - 1]);
            else
                if(i > 0)
                    forward[i] = forward[i - 1];
            min = Math.min(prices[i], min);
            // the second transaction
            if(prices[prices.length - 1 - i] < max)
                backward[prices.length - 1 - i] = Math.max(max - prices[prices.length - 1 - i], backward[prices.length - i]);
            else
                if(i > 0)
                    backward[prices.length - 1 - i] = backward[prices.length - i];
            max = Math.max(prices[prices.length - 1 - i], max);
        }
        // find out the max profit combined 2 transactions
        int res = 0;
        for(int i = 0; i < prices.length; i++)
            res = Math.max(forward[i] + backward[i], res);
        return res;
    }
    
    public int maxProfit(int[] P) {
        if(P.length < 2) return 0;
        int[] one = new int[P.length];
        int minP = P[0];
        for(int i = 1; i < P.length; i++) {
            minP = Math.min(minP, P[i]);
            one[i] = Math.max(one[i - 1], P[i] - minP);
        }
        int[] two = new int[P.length];
        int maxP = P[P.length - 1];
        for(int i = P.length - 2; i >= 0; i--) {
            maxP = Math.max(maxP, P[i]);
            two[i] = Math.max(two[i + 1], maxP - P[i]);
        }
        int res = Integer.MIN_VALUE;
        for(int i = 0; i < P.length; i++) {
            res = Math.max(one[i] + two[i], res);
        }
        return res;
    }
    
    public int maxProfit(int[] prices) {
        int hold1 = Integer.MIN_VALUE, hold2 = Integer.MIN_VALUE;
        int release1 = 0, release2 = 0;
        for(int i:prices){                              // Assume we only have 0 money at first
            release2 = Math.max(release2, hold2+i);     // The maximum if we've just sold 2nd stock so far.
            hold2    = Math.max(hold2,    release1-i);  // The maximum if we've just buy  2nd stock so far.
            release1 = Math.max(release1, hold1+i);     // The maximum if we've just sold 1nd stock so far.
            hold1    = Math.max(hold1,    -i);          // The maximum if we've just buy  1st stock so far. 
        }
        return release2; ///Since release1 is initiated as 0, so release2 will always higher than release1.
    }
}