I am implementing dp for this [question][1] 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
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[2][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.
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
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…
Yes,it can be optimised by calculating maximum profit gained by selling shares on ith day in constant time.Anyway,I was talking about space complexity and its good to know it’s working with your logic too.