Best Time to Buy and Sell Stock IV

Question

Say you have an array for which the i-th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

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

LeetCodeleetcode.com/problems/best-time-to-buy-and-sell-stock-iv

Solution

public int maxProfit(int k, int[] prices) {
    if (k == 0) {
        return 0;
    }
    if (k >= prices.length / 2) {
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                profit += prices[i] - prices[i - 1];
            }
        }
        return profit;
    }
    /*
        best[i][j] 表示前i天，至多进行j次交易时的最大获益
        sell[i][j] 表示前i天，至多进行j次交易，并且第i天卖出手中的股票时的最大获益
        状态转移:

        sell[i][j] = max(best[i - 1][j - 1], sell[i - 1][j]) + prices[i] - prices[i - 1]
        best[i][j] = max(best[i - 1][j], sell[i][j])
    
    */
    int n = prices.length;
    int[][] sell = new int[n + 1][n + 1]; // sell[i][j] 表示前i天，至多进行j次交易，第i天必须sell的最大获益
    int[][] best = new int[n + 1][n + 1]; // best[i][j] 表示前i天，至多进行j次交易，第i天可以不sell的最大获益

    sell[0][0] = best[0][0] = 0;
    for (int i = 1; i <= k; i++) {
        sell[0][i] = best[0][i] = 0;
    }

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