# 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, and an integer `k`.

Find the maximum profit you can achieve. You may complete at most `k` transactions.

**Note:** You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

**Example 1:**

```
Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.
```

**Example 2:**

```
Input: k = 2, prices = [3,2,6,5,0,3]
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
```

### **Solution**: Exhaustive DP

There are three variables to this problem:

1. The day we are on
2. Whether we current own or not own the stock
3. Have we used all our transactions yet

*Combinations of these three will make up every possible state of this problem*

### Inductive Rule for each day:

To own a stock today: 

1. Owned it yesterday and held
2. Did not own it yesterday and bought

To not own a stock today:

1. Not own it yesterday and held
2. Owned it yesterday and sold

Defining the decrement of k as occurring after a sale, we have the inductive equations:

own(today, k) = max(own(prevDay, k) , notOwn(prevDay, k) - price(today))

notOwn(today, k) = max(notOwn(prevDay, k) , own(prevDay, **k - 1**) + price(today))

```java
class Solution {
    public int maxProfit(int k, int[] prices) {
        
        if (prices.length == 0 || k == 0) return 0;
        int length = prices.length;
        //two arrays
        int[][] own = new int[length][k];
        int[][] notOwn = new int[length][k];
        
        int max = 0;
        //base case, first day all buys equal -prices[i]
        // own[0][0] = -prices[0];
        for(int i = 0; i < k; i++){
            own[0][i] = Integer.MIN_VALUE;
        }
        own[0][0] = -prices[0];
        
        for(int i = 1; i < length; i++){
            for(int j = 0; j < k; j++){
                own[i][j] = Math.max(own[i - 1][j], notOwn[i - 1][j] - prices[i]);
                if(j == 0) continue; //base case: notOwn, no transaction == 0. Default value
                notOwn[i][j] = Math.max(notOwn[i - 1][j], own[i - 1][j - 1] + prices[i]);
                max = Math.max(notOwn[i][j], max);
            }
            //check kth at end
            max = Math.max(prices[i] + own[i - 1][k - 1], max);
            
            
        }
        
        return max;
        
    }
}
```

TC: O(N \* K)

SC:O(N \* K \* 2)

Space can be optimized:

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

        int[] own = new int[k];
        int[] notOwn = new int[k];
        
        int max = 0;
        
        //base case, first day all buys equal -prices[i]

        for(int i = 0; i < k; i++){
            own[i] = Integer.MIN_VALUE;
        }
        own[0] = -prices[0];
        
        for(int i = 1; i < length; i++){
            for(int j = 0; j < k; j++){
                own[j] = Math.max(
                    own[j],
                    notOwn[j] - prices[i]
                );
                //base case: No transactions done yet. Nothing to sell
                if(j == 0) continue; 
                
                notOwn[j] = Math.max(
                    notOwn[j],
                    own[j - 1] + prices[i]
                );
                max = Math.max(notOwn[j], max);
            }
            
            //check kth at end
            max = Math.max(
                prices[i] + own[k - 1],
                max
            );
        }
        return max;
    }
}
```

TC: O(K)