Best Time to Buy and Sell Stock IV

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 k transactions.

Note:
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 k, int[] prices) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }
        int n = prices.length;
        if (k >= n / 2) {
            int profit = 0;
            for (int i = 0; i < n - 1; i++) {
                if (prices[i + 1] > prices[i]) {
                    profit += prices[i + 1] - prices[i];
                }
            }
            return profit;
        }
        int profits[] = new int[k + 1];
        int balances[] = new int[k + 1];
        for (int i = 0; i <= k; i++){
            balances[i] = Integer.MIN_VALUE;
            profits[i] = 0;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= k; j++) {
                profits[j] = Math.max(balances[j] + prices[i], profits[j]);
                balances[j] = Math.max(profits[j - 1] - prices[i], balances[j]);
            }
        }
        return profits[k];
    }
}

============

public class Solution {
    public int maxProfit(int k, int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        if (k >= prices.length / 2) {
            int res = 0;
            for (int i = 0; i < prices.length - 1; i++) {
                if (prices[i + 1] > prices[i]) {
                    res += prices[i + 1] - prices[i];
                }
            }
            return res;
        }
        int afterSell[] = new int[k + 1];
        int afterBuy[] = new int[k + 1];
     
        for (int i = 0; i <= k; i++){
            afterBuy[i] = Integer.MIN_VALUE;
            afterSell[i] = 0;
        }
     
        for (int i = 0; i < prices.length; i++) {
            for (int j = 1; j <= k; j++) {
                afterSell[j] = Math.max(afterSell[j], afterBuy[j] + prices[i]);
                afterBuy[j] = Math.max(afterBuy[j], afterSell[j - 1] - prices[i]);
            }
        }
        return afterSell[k];
    }
}

==========

public class Solution {
    public int maxProfit(int k, int[] prices) {
        if (k == 0 || prices == null || prices.length == 0) return 0;
        int n = prices.length;
        if (k >= n / 2) {
            int res = 0;
            for (int i = 1; i < n; i++) {
                if (prices[i] > prices[i - 1]) {
                    res += prices[i] - prices[i - 1];
                }
            }
            return res;
        }
        int[] sell = new int[k + 1];
        int[] buy = new int[k + 1];
        Arrays.fill(buy, Integer.MIN_VALUE);
        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= k; j++) {
                sell[j] = Math.max(sell[j], buy[j] + prices[i]);
                buy[j] = Math.max(buy[j], sell[j - 1] - prices[i]);
            }
        }
        return sell[k];
    }
}