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:

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.

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

int maxProfit(int k, vector<int> &prices)
{
    if (prices.empty())
        return 0;
    int n = prices.size();
    vector<vector<int>> dp(k + 1, vector<int>(n, 0));
    for (int i = 1; i <= k; i++)
    {
        int maximumValue = INT_MIN;
        for (int d = 1; d < n; d++)
        {
            maximumValue = max(maximumValue, 
            dp[i - 1][d - 1] - prices[d - 1]);
            dp[i][d] = max(dp[i][d - 1],
             maximumValue + prices[d]);
        }
    }
    return dp[k].back();
}

int main()
{
    int k = 2;
    vector<int> prices = {2, 4, 1};

    cout << maxProfit(k, prices);

    return 0;
}