**Difficulty: Hard**

**Frequency: N/A**

Say you have an array for which the *i*^{th} element is the price of a given stock on day *i*.

Design an algorithm to find the maximum profit. You may complete at most **k** transactions.

**Note:**

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

**Test Cases:**

**Solution 1:**

**Data structure:**

**Steps:**

**Complexity:**

**Code:**

class Solution { public: int maxProfit(int k, vector<int>& prices) { int n = prices.size(); if (k >= n / 2) return helper(prices); vector<vector<int>> dp(k + 1, vector<int>(n, 0)); for (int i = 1; i <= k; i++) { int tmpMax = -prices[0]; for (int j = 1; j < n; j++) { dp[i][j] = max(dp[i][j - 1], tmpMax + prices[j]); tmpMax = max(tmpMax, dp[i - 1][j - 1] - prices[j]); } } return dp[k][n - 1]; } int helper(vector<int>& prices) { int n = prices.size(), result = 0; for (int i = 1; i < n; i++) { if (prices[i] > prices[i - 1]) { result += prices[i] - prices[i - 1]; } } return result; } };

**Solution 2:**

**Data structure:**

**steps:**

**Complexity**:

**Code**:

**Submission errors:**

**Things to learn:**