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

&nbsp;
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.


&nbsp;
Constraints:


	0 &lt;= k &lt;= 100
	0 &lt;= prices.length &lt;= 1000
	0 &lt;= prices[i] &lt;= 1000


class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        buy = [-inf] * (k+1)
        sell = [0] * (k+1)
        for price in prices:
            for i in range(1,k+1):
                    buy[i] = max(buy[i],sell[i-1]-price)
                    sell[i] = max(sell[i],buy[i]+price)
        return sell[-1]
class Solution {
    public int maxProfit(int k, int[] prices) {
        int transaction = k;
        int N = prices.length;
        int[][][]dp =new int[N][2][k+1];
        for(int i=0;i<N;i++){
            for(int j =0;j<2;j++){
                for(int tran=0;tran<=k;tran++){
                    dp[i][j][tran] = -1;
                }
            }
        }//init dp
        return profit(0,1,k,prices,dp);
    }
    int profit(int index, int buy, int transaction , int[]prices, int[][][]dp){
        if(transaction == 0){
            return 0;
        }
        if(index == prices.length){
            return 0;
        }
        if(dp[index][buy][transaction] != -1){
            return dp[index][buy][transaction];
        }
        int profit =0;
        if(buy == 1){
            profit = Math.max(-prices[index] + profit(index+1,0,transaction,prices,dp),
                               0 + profit(index+1,1,transaction,prices,dp));
        }else{
            profit = Math.max(prices[index] + profit(index+1,1,transaction-1,prices,dp),
                              0 + profit(index+1, 0, transaction,prices,dp));
        }
        dp[index][buy][transaction] = profit;
        return dp[index][buy][transaction];
    }
}
class Solution {
public:
    int solve(int ind, int buy, int k, vector<int>& prices, vector<vector<vector<int>>>& dp){
        if(k==0 || ind==prices.size()) return 0;
        if(dp[ind][buy][k] != -1) return dp[ind][buy][k];
        if(buy){
            return dp[ind][buy][k] = max(-prices[ind]+solve(ind+1, 0, k, prices, dp), solve(ind+1, 1, k, prices, dp));
        }
        return dp[ind][buy][k] = max(prices[ind]+solve(ind+1, 1, k-1, prices, dp), solve(ind+1, 0, k, prices, dp));
    }
    int maxProfit(int k, vector<int>& prices) {
        vector<vector<vector<int>>> dp(prices.size(), vector<vector<int>> (2, vector<int> (k+1, -1)));
        return solve(0, 1, k, prices, dp);
    }
};
var maxProfit = function(k, prices) {
    const len = prices.length;
    let dp = new Array(len).fill(0);
    dp = dp.map(() => new Array(2).fill(0).map(() => new Array(k+1).fill(-1)));
    const solve = (day = 0, cap = k, buy = 0) => {
        if(day == len || cap == 0) return 0;

        if(dp[day][buy][cap] != -1) return dp[day][buy][cap];

        let take, notake;
        notake = solve(day + 1, cap, buy);
        if(buy == 0) {
            take = solve(day + 1, cap, 1) - prices[day];
        } else {
            take = solve(day + 1, cap - 1, 0) + prices[day];
        }
        return dp[day][buy][cap] = Math.max(take, notake)
    };
    return solve();
};
Best Time to Buy and Sell Stock IV