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

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:

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)