<p>You are given an integer array <code>prices</code> where <code>prices[i]</code> is the price of a given stock on the <code>i<sup>th</sup></code> day, and an integer <code>k</code>.</p>

<p>Find the maximum profit you can achieve. You may complete at most <code>k</code> transactions: i.e. you may buy at most <code>k</code> times and sell at most <code>k</code> times.</p>

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

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

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

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> k = 2, prices = [3,2,6,5,0,3]
<strong>Output:</strong> 7
<strong>Explanation:</strong> 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.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= k &lt;= 100</code></li>
	<li><code>1 &lt;= prices.length &lt;= 1000</code></li>
	<li><code>0 &lt;= prices[i] &lt;= 1000</code></li>
</ul>

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        int n=prices.size();
        // vector<vector<int>> dp(n,vector<int>(4,0));
        // return memo(dp,prices,0,4);

        vector<int> prev(2*k+1,0);
        for(int i=n-1;i>-1;i--){
            vector<int> curr(2*k+1,0);
            for(int buy=1;buy<=2*k;buy++){
                if(buy%2==0){
                    curr[buy]=max(prev[buy],-prices[i]+prev[buy-1]);
                }
                else curr[buy]=max(prev[buy],prices[i]+prev[buy-1]);
            }
            prev=curr;
        }
        return prev[2*k];

    }
};
// class Solution {
// public:
    
//     int maxProfit(int k, vector<int>& prices) {
//         ios_base::sync_with_stdio(false);
//         cin.tie(NULL);
//         int n=prices.size();
//         // vector<vector<int>> dp(n,vector<int>(4,0));
//         // return memo(dp,prices,0,4);

//         vector<vector<int>> dp(n+1,vector<int>(2*k+1,0));
//         for(int i=n-1;i>-1;i--){
//             for(int buy=1;buy<=2*k;buy++){
//                 if(buy%2==0){
//                     dp[i][buy]=max(dp[i+1][buy],-prices[i]+dp[i+1][buy-1]);
//                 }
//                 else dp[i][buy]=max(dp[i+1][buy],prices[i]+dp[i+1][buy-1]);
//             }
//         }
//         return dp[0][2*k];

//     }
// };
15728