0188. Best Time to Buy and Sell Stock IV

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv

Description

You are given an integer array prices where prices[i] is the price of a given stock on the ith day, and an integer k.

Find the maximum profit you can achieve. You may complete at most k transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example 1:

**Input:** k = 2, prices = [2,4,1]
**Output:** 2
**Explanation:** Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2:

**Input:** k = 2, prices = [3,2,6,5,0,3]
**Output:** 7
**Explanation:** Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

Constraints:

• 0 <= k <= 100

• 0 <= prices.length <= 1000

• 0 <= prices[i] <= 1000

ac

class Solution {
    public int maxProfit(int k, int[] prices) {
        // edge cases
        if (prices == null || prices.length <= 1 || k < 1) return 0;

        int len = prices.length;
        // quick solution, when k > half, it means unlimited transaction
        if (k >= len / 2) return helper(prices);

        int[][] dp = new int[k+1][len];
        for (int i = 1; i <= k; i++) {

            int afterBuyProfit = dp[i-1][0] - prices[0];  //  means max profit after buy 1 stock 

            for (int j = 1; j < len; j++) {
                // dp[i][j] means max profit under: 1) at most i transaction, 2) at day j
                // this function means, comparing selling at day j-1 or day j, which one has max profit
                dp[i][j] = Math.max(dp[i][j-1], prices[j] + afterBuyProfit);

                // which day to buy? if day j price is lower, buying result greater profit, so buy it.
                // it basically pick the min price like #121
                afterBuyProfit = Math.max(afterBuyProfit, dp[i-1][j-1] - prices[j]);
            }
        }

        // result
        return dp[k][len-1];
    }

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

class Solution {
    public int maxProfit(int k, int[] prices) {
        // edge cases
        if (prices == null || prices.length == 0 || k <= 0) 
            return 0;

        // shotcut
        if (k > prices.length / 2) {
            int res = 0;
            for (int i = 1; i < prices.length; i++) {
                if (prices[i] > prices[i-1]) res += prices[i] - prices[i-1];
            }
            return res;
        }


        int[][] profits = new int[k+1][prices.length];

        for (int r = 1; r <= k; r++) {
            int buy = -prices[0], sell = 0;
            for (int c = 1; c < prices.length; c++) {
                buy = Math.max(buy, profits[r-1][c-1] - prices[c]);
                sell = Math.max(sell, buy + prices[c]);
                profits[r][c] = sell;
            }
        }

        return profits[k][prices.length-1];
    }
}