Buy and Sell Stock

121 I

You can only sell and buy once 1. mantain a profit and low int

122 II

You can buy and sell many times 1. greedy algo 2. if profitable, add on

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

123 III

You can only buy and sell twice 1. DP

public int maxProfit(int[] prices) {
    int buy1 = - prices[0], buy2 = - prices[0];
    int sell1 = 0, sell2 = 0;

    for (int i=1; i<prices.length; i++){
    //  buy1每天都跟新購買比較
        buy1 = Math.max(buy1, - prices[i]);          // max profit of first buy
        sell1 = Math.max(sell1, buy1 + price[i]);   // max profit of first sell
        buy2 = Math.max(buy2, sell1 - price[i]);    // max profit of second buy
        sell2 = Math.max(sell2, buy2 + price[i]);   // max profit of second sell
    }    
    return sell2;
}

188 IV

You can buy and sell for k times

• Hold stock and unhold stock tables

• State: 1. hold[i][j]: the max profit in ith day and j transaction with holding stock 2. unhold[i][j]: the max profit in ith day and j transaction without holding stock

• Func: 1. hold[i][j] = max(hold[i-1][j], unhold[i-1][j]-price[i]) 2. unhold[i][j] = max(unhold[i-1][j], hold[i-1][j-1]+ price[i])

• Init: hold[0][0-k] = - price[0], hold[i][0] = max(hold[i-1][0], -price[i])

• Ans: unhold[len][k]

public int maxProfit(int k, int[] prices) {
    int len = prices.length;
    if (k >= len/2) return helper(prices);

    // the max profit in ith day and k transaction with holding stock
    int[][] hold = new int[len][k+1];
    // the max profit in ith day and k transaction without holding stock
    int[][] unhold = new int[len][k+1];

    // init
    for(int j=0; j<=k; j++){
        hold[0][j] = -prices[0];
    }

    for(int i=1; i<len; i++){
        hold[i][0] = Math.max(hold[i-1][0], -prices[i]);
    }

    // func
    for(int i=1; i<len; i++){
        for(int j=1; j<=k; j++){
            hold[i][j] = Math.max(hold[i-1][j], unhold[i-1][j] - prices[i]);
            unhold[i][j] = Math.max(unhold[i-1][j], hold[i-1][j-1] + prices[i]);
        }
    }
    return unhold[len-1][k];
}

private int helper(int[] prices){
    int profit = 0;
    for(int i=1; i<prices.length; i++){
        if(prices[i] - prices[i-1] > 0){
            profit += prices[i] - prices[i-1];
        }
    }
    return profit;
    }

714 With transaction fee

You can buy and sell many times

public int maxProfit(int[] prices, int fee) {
    // 2 situations: buy and sell

    int buy = -prices[0];
    int sell = 0;

    for (int i=1; i<prices.length; i++){
        buy = Math.max(buy, sell - prices[i]);
        sell = Math.max(sell, buy + prices[i] - fee);
    }
    return sell;
}

309 With 1 day cool down

You can buy and sell many times

• Func: buy[i] = max(buy[i-1], sell[i-2]-price[i]), sell[i] = max(sell[i-1], buy[i-1]+price[i])

• O(n) space

public int maxProfit(int[] prices) {
    public int maxProfit(int[] prices) {
    if(prices == null || prices.length == 0) return 0;

    int[] buy = new int[prices.length];
    int[] sell = new int[prices.length];
    buy[0] = -prices[0];

    for(int i=1; i<prices.length; i++){
        buy[i] = Math.max(buy[i-1], i == 1 ? -prices[i] : sell[i-2]-prices[i]);
        sell[i] = Math.max(sell[i-1], buy[i-1]+prices[i]);
    }
    return sell[prices.length-1];
}

• O(1) space

public int maxProfit(int[] prices) {
    if(prices == null || prices.length == 0) return 0;

    int buy = -prices[0];
    int preSell = 0;
    int curSell = 0;

    for(int i=1; i<prices.length; i++){
        int tmp = curSell;
        buy = Math.max(buy, preSell - prices[i]);
        curSell = Math.max(curSell, buy + prices[i]);
        preSell = tmp;
    }
    return curSell;
}