Best Time to Buy and Sell Stock IV

1package pkg5leetcode.official75;2 3/*4 * Best Time to Buy and Sell Stock IV | LC 1885 * APPROACH: DP buy[k] and sell[k] states per day.6 * COMPLEXITY: Time O(nk), Space O(k)7 */8public class official75_LC188BestTimeToBuyAndSellStockIV {9    static int maxProfit(int k, int[] prices) {10        if (k >= prices.length / 2) {11            int profit = 0;12            for (int i = 1; i < prices.length; i++)13                if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];14            return profit;15        }16        int[] buy = new int[k + 1], sell = new int[k + 1];17        java.util.Arrays.fill(buy, Integer.MIN_VALUE / 2);18        for (int p : prices)19            for (int t = 1; t <= k; t++) {20                buy[t] = Math.max(buy[t], sell[t - 1] - p);21                sell[t] = Math.max(sell[t], buy[t] + p);22            }23        return sell[k];24    }25 26    public static void main(String[] args) {27        check(maxProfit(2, new int[]{2,4,1}) == 2, "case1");28        check(maxProfit(2, new int[]{3,2,6,5,0,3}) == 7, "case2");29        System.out.println("all tests passed");30    }31 32    static void check(boolean cond, String name) {33        if (!cond) throw new AssertionError("FAILED: " + name);34        System.out.println("  PASS " + name);35    }36}