help needed in Buy Sell stock problem with atmost k transactions

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


[2]


  [1]: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/description/
  [2]: 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[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.

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…

@hemanth_1 please reply

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

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.

1 Like