Maximum profit from k buys and sells

Given an array of numbers representing the stock prices of a company in chronological order and an integer k, return the maximum profit you can make from k buys and sells. You must buy the stock before you can sell it, and you must sell the stock before you can buy it again.

For example, given k = 2 and the array [5, 2, 4, 0, 1], you should return 3.

Example:

Input:  k = 2, arr = [5,2,4,0,1]
Output: 3

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 = {5, 2, 4, 0, 1};

    cout << maxProfit(k, prices);

    return 0;
}