188. Best Time to Buy and Sell Stock IV

You are given an integer array prices where prices[i] is the price of a given stock on the ith day. Design an algorithm to find the maximum profit. You may complete at most k transactions.

class Solution {
    public int maxProfit(int k, int[] prices) {
        // dp[i,j] = max profit in index i, with transaciton j
        // sold[i,j] = max(sold[i-1,j], hold[i-1, j]+prices[i]);
        // hold[i,j] = max(hold[i-1,j], j-1<K ? {sold[i-1, j-1]-prices[i]; j++} : min);
        // base case: sold[i, 0] = 0, hold[i, 0] = 0;sold[0, j]=0, hold[0,j] = -prices[0] (j>0);
        if (k<1 || prices.length<1) return 0;
        
        int[][] sold = new int[prices.length][k+1];
        int[][] hold = new int[prices.length][k+1];
        for(int j=1; j<k+1; j++){
            hold[0][j]= -prices[0];
        }
        
        int res = 0;
        for(int i=1; i<prices.length;i++){
            for (int j=1; j<k+1; j++){
                sold[i][j]=Math.max(sold[i-1][j], hold[i-1][j]+prices[i]);
                hold[i][j]=Math.max(hold[i-1][j], sold[i-1][j-1]-prices[i]);
                if (i == prices.length-1 && sold[i][j]>res){
                    res = sold[i][j];
                }
            }
        }
        
        return res;           
    }
}

memory optimize

class Solution {
    public int maxProfit(int k, int[] prices) {
        // dp[i,j] = max profit in index i, with transaciton j
        // sold[i,j] = max(sold[i-1,j], hold[i-1, j]+prices[i]);
        // hold[i,j] = max(hold[i-1,j], j-1<K ? {sold[i-1, j-1]-prices[i]; j++} : min);
        // base case: sold[i, 0] = 0, hold[i, 0] = 0;sold[0, j]=0, hold[0,j] = -prices[0] (j>0);
        
        // max of transactions =prices.length/2;
        k = Math.min(k, prices.length/2);
        if (k<1 || prices.length<1) return 0;
        
        int[] sold = new int[k+1];
        int[] hold = new int[k+1];
        for (int j=1; j<k+1; j++){
             hold[j] = -prices[0];
        }

        for(int i=1; i<prices.length;i++){
            int preSold = 0;
            for (int j=1; j<k+1; j++){
                int prevHold = hold[j];
                hold[j]=Math.max(hold[j], preSold-prices[i]);
                preSold = sold[j];
                sold[j]=Math.max(sold[j], prevHold+prices[i]);
            }
        }
        
        return sold[k];         
    }
}