# help needed in Buy Sell stock problem with atmost k transactions

I am implementing dp for this [question] but there is a test case where K=1e9 . This test case gives rumtime error whenever I submit can someone please help me. Here is my

``````


: https://ideone.com/Q6r1nf``````

You can’t declare such a big array if k is 10^9

I think you can use a flag variable for iterating current row,as the solution needs only the elements of current row and its previous row,so maintaining a array of size 2*(n+1) will not give runtime error.Here is the implementation:

static int maxProfit(int[] price, int n, int k)
{
int[][] profit = new int[n + 1];

``````   int f=1;
for (int i = 1; i <= k; i++)
{
for (int j = 1; j < n; j++)
{
int max_so_far = 0;
for (int m = 0; m < j; m++)
max_so_far = Math.max(max_so_far, price[j] -price[m] + profit[f^1][m]);

profit[f][j] = Math.max(profit[f] [j - 1],max_so_far);
}
f^=1;
}
return profit[f^1][n - 1];
}
``````

This is a very useful technique to improve space complexity in DP problems. It can also be applied in knapsack and subset sum problem. I learnt this technique somewhere on internet.
Try to do it this way and see if it works or not.

1 Like

I know that but for an array a size n there can be at most n transactions so that’s why I used k=min(k,n) for the failing test case n turns out to be 10000 then why am I getting runtime error

you’re declaring an array of size k*n

yes but it’s a 2d array can I not declare a 2d array of 10000X10000?
Also , apart from that can you tell me how to do this problem then . Any other method then dp? Help please…

Your approach is O(kn^2) which might get TLE . However your approach to minimize space usage seems to work with my logic . Thanks 