It is a basic `DP`

question.

You will need to store maximum profit you can make using a particular number of transactions till a particular day.

Let's create an array `dp[][]`

where `dp[i][j]`

will represent the maximum profit you can make using `i`

transactions till the end of the `j`

^{th} day.

This requires a space complexity of **O(K x N)** where **K** is the number of transactions and **N** is the size of the array.

Also, the maximum transactions which are anyway possible is **N/2** as you can purchase a stock and sell it on another day and keep doing it repeatedly.

*(Forget the profits for the time being, focus on the maximum transactions possible)*

Hence this puts an upper limit on the value of **K**. It has to be less than **N/2**.

Now to find the maximum profit which can be made using **k** transactions till **j**^{th} day, we have two choices:

- Don't do any transaction on the
**j**^{th}day.

This choice can be represented by`dp[k][j] = dp[k][j-1]`

. i.e. maximum profit which can be made using same number of transactions but till the**j-1**^{th}day - Sell any stock on
**j**^{th}day.purchased earlier on some**i**^{th}day in a way that it yields maximum profit.

This choice can be represented by :

`dp[k][j] = prices[j] - prices[i] + dp[k][i-1].`

This can be found out by maintaining a**maxi**variable which stores the maximum value of`dp[k][i-1]-prices[i]`

. This**maxi**variable reduce the time complexity from`O(K*N*N)`

to`O(K*N)`

.

Here is the code representing the same:

**( Without maxi variable -- Will timeout!!)**

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

**( With maxi variable -- All test cases passed but Memory Limit Exceeded!!)**

```
class Solution {
public:
int maxProfit(int K, vector<int>& prices) {
int N=prices.size();
if(N<=1)return 0;
K=min(K,(N+1)/2);
vector<vector<int>>dp(K+1,vector<int>(N+1,0));
for(int k=1;k<=K;k++){
int maxi = -prices[0];
for(int j=1;j<N;j++){
dp[k][j]=max(dp[k][j-1],prices[j]+maxi);
maxi=max(maxi,-prices[j]+dp[k-1][j]);
}
}
return dp[K][N-1];
}
};
```

However with little more observation, we can see that we can reduce the space complexity from **O(K x Len)** to **O(2 x Len)**, since we only need to refer to the `i-1`

^{th} transaction. We can create a `dp[2][len]`

array. `dp[i]`

can be replaced with `dp[1]`

and `dp[i-1]`

with `dp[0]`

. After the **j**^{th} for loop, we just need to update the `dp[0]`

with `dp[1]`

.

Finally return `dp[1][len-1]`

.

Here is the code indicating this optimization.

*Gets Accepted wihout TLE and without Memory Limit Exceeded. Hurray!!*

```
class Solution {
public:
int maxProfit(int K, vector<int>& A) {
int N = A.size();
if(N<=1)return 0;
K=min(K,(N+1)/2);
vector<vector<int>>dp(2,vector<int>(N+1,0));
for(int k=1;k<=K;k++){
int maxi = -A[0];
for(int j=1;j<N;j++){
dp[1][j]=max(dp[1][j-1],A[j]+maxi);
maxi=max(maxi,-A[j]+dp[0][j]);
}
dp[0]=dp[1];
}
return dp[1][N-1];
}
};
```