> For the complete documentation index, see [llms.txt](https://ucan.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ucan.gitbook.io/notes/dynamic-programming/untitled.md).

# 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.](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/)

```java
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

```java
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];         
    }
}
```