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).

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

Solution I: 2D DP, TLE

The local array tracks maximum profit of j transactions & the last transaction is on ith day. The global array tracks the maximum profit of j transactions until ith day.

public class Solution {
    public int maxProfit(int k, int[] prices) {
        if (prices.length == 0) {
            return 0;
        }    

    // solve the TLE problem   
    if(k>=prices.length/2){
        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;
    }


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

        for (int j = 1; j <= k; j++) {
            for (int i = 1; i < prices.length; i++) {
                int diff = prices[i] - prices[i-1];
                local[i][j] = Math.max(res[i-1][j-1] + Math.max(diff, 0), local[i-1][j] + diff);
                res[i][j] = Math.max(res[i-1][j], local[i][j]);
            }
        }

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

Solution II: General version of Best Time to Buy and Sell Stock III

https://leetcode.com/discuss/69340/clean-java-dp-o-nk-solution-with-o-k-space

public int maxProfit(int k, int[] prices) {
    if(k>=prices.length/2){
        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;
    }

    int[] maxProfit = new int[k+1];
    int[] lowPrice = new int[k+1];
    for(int i=0; i<lowPrice.length; i++) lowPrice[i]=Integer.MAX_VALUE;
    for(int p : prices){
        for(int i=k; i>=1; i--){
            maxProfit[i] = Math.max(maxProfit[i],p-lowPrice[i]);
            lowPrice[i] = Math.min(lowPrice[i],p-maxProfit[i-1]);
        }
    }
    return maxProfit[k];
}