Problem Statement

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.

Problem Link

Best Time to Buy and Sell Stock IV - LeetCode

Reference Video

https://www.youtube.com/watch?v=oDhu5uGq_ic&t=7s

Recursive Equation

Code

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if(!n)
            return 0;
        int dp[k+1][n];
        
        for(int i=0;i<=k;i++)
        {
            
            for(int j=0;j<n;j++)
            {
                if(!i||!j)
                    dp[i][j] = 0;
                
                else
                {
                   
                    int cost = INT_MIN;
                    for(int k=0;k<j;k++)
                    {
                        cost = max(cost,prices[j]-prices[k]+dp[i-1][k]);
                    }
                   
                    dp[i][j] = max(dp[i][j-1],cost);
                }
            }
        }
        return dp[k][n-1];
    }
};
// Time Complexity : O(n^3),   Space Complexity : O(n^2)

Optimized Approach

Code

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if(!n)
            return 0;
        **if(k>n)
            k=n;**
        int dp[k+1][n];
        
        for(int i=0;i<=k;i++)
        {
            int maxDiff = INT_MIN;
            for(int j=0;j<n;j++)
            {
                if(!i||!j)
                    dp[i][j] = 0;
                
                else
                {
                    maxDiff = max(maxDiff,dp[i-1][j-1]-prices[j-1]);
                    dp[i][j] = max(dp[i][j-1],maxDiff+prices[j]);
                }
            }
        }
        return dp[k][n-1];
    }
};
// Time Complexity : O(n^2),   Space Complexity : O(n^2)