Best Time to Buy and Sell Stock

One transaction

• Time: O(n)
• Space: O(n)

public int maxProfit(int[] prices) {
    if (prices == null || prices.length <= 1) return 0;
    int lowPrice = prices[0], maxProfit = 0;
    for (int i = 1; i < prices.length; i++) {
        lowPrice = Math.min(lowPrice, prices[i]);
        maxProfit = Math.max(maxProfit, prices[i] - lowPrice);
    }
    return maxProfit;
}

Many transactions

• Time: O(n)
• Space: O(n)

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

Two transactions

• Time: O(n)
• Space: O(n)

public int maxProfit(int[] prices) {
    if (prices.length <= 1) return 0;
    int[] preDP = new int[prices.length], postDP = new int[prices.length];
    int min = prices[0], max = prices[prices.length - 1];
    for (int i = 1; i < prices.length; i++) {
        min = Math.min(min, prices[i]);
        preDP[i] = Math.max(preDP[i - 1], prices[i] - min);
    }
    for (int i = prices.length - 2; i >= 0; i--) {
        max = Math.max(max, prices[i]);
        postDP[i] = Math.max(postDP[i + 1], max - prices[i]);
    }
    int maxProfit = 0;
    for (int i = 0; i < prices.length; i++) {
        if (preDP[i] + postDP[i] > maxProfit) {
            maxProfit = preDP[i] + postDP[i];
        }
    }
    return maxProfit;
}

K transactions

• Time: O(nk)
• Space: O(nk)

public int maxProfit(int k, int[] prices) {
    int n = prices.length;
    if (n <= 1)
        return 0;

    if (k >= n / 2) {
        int maxProfit = 0;
        for (int i = 1; i < n; i++) {
            if (prices[i] > prices[i - 1])
                maxProfit += prices[i] - prices[i - 1];
        }
        return maxProfit;
    }

    int[][] dp = new int[k + 1][n];
    for (int i = 1; i <= k; i++) {
        int max = dp[i - 1][0] - prices[0];
        for (int j = 1; j < n; j++) {
            dp[i][j] = Math.max(dp[i][j - 1], prices[j] + max);
            max = Math.max(max, dp[i - 1][j] - prices[j]);
        }
    }
    return dp[k][n - 1];
}

Best Time to Buy and Sell Stock with Cooldown

• Time: O(n)
• Space: O(n)

public int maxProfit(int[] prices) {
    if (prices.length <= 1) return 0;
    int profit1 = 0, profit2 = 0;
    for (int i = 1; i < prices.length; i++) {
        int temp = profit1;
        profit1 = Math.max(profit1 + prices[i] - prices[i - 1], profit2);
        profit2 = Math.max(profit2, temp);
    }
    return Math.max(profit1, profit2);
}