# Best Time to Buy and Sell Stock IV

• 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 jth day, we have two choices:

1. Don't do any transaction on the jth 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-1th day
2. Sell any stock on jth day.purchased earlier on some ith 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 jth 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];
}
};

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.