Leetcode : Best Time To Buy And Sell Stock IV

Here’s the problem statement -> link

Hmm, let’s get started with our little stock market today. Here are some of the rules to ponder,

1. You can make at most ‘k’ transactions.
2. You cannot engage in multiple transactions. (i.e. Harshad Mehta, if you have bought a stock, before buying any new stock you have to sell this pre-possessed stock)

This seemed like an exhaustive problem to me, wherein I just have to exhaustively choose when I buy a stock & when to sell that stock, plus keep in mind that I’ve to maximize the profits.

Let’s recursively think of my choices under the conditions,

At any point I can either buy a stock or I can sell an already bought stock. I cannot buy any new stock before I sell my already possessed stock.

So, what I can do is, I can keep track of whether I’ve bought a stock or not.

1 > If I’ve bought a stock, then I can either sell it right now or I can sell it later.

2 > If I haven’t bought a stock, then I can either buy one right now or I can buy it later.

A recursive solution would be something like this ->

Driver Function

recursive function

My base case is pretty straightforward, either I get done with all the transactions, or I run out of my prices array.

I’m keeping the count of bought and sold, by using a variable bought, if bought is even(0, 2, 4, 6..) that means I haven’t bought any stock, if it’s odd(1, 3, 5, 7..) that means I’ve already bought a stock.

In case I’ve previously bought a stock, I have two options ->

I can either sell it, I can skip selling it right now and might sell it later. Similarly, if I haven’t bought any stocks previously, then I can either buy a stock right now, or skip today and maybe buy it later.

So, I’m exhaustively exploring all the ways, and returning the one which return the max value, in this manner I can easily maximize my profits.

But, here’s the thing, the complexity of recursive solution will be O(2 ^ N), where N is the size of prices array, because at every call I have two options either to <(buy/sell) plus skip>

No issues, as I can simply memoize my recursive solution, because there will be many overlapping subproblems/subcases. And I need not to compute those cases again and again.

A memoized solution would be something like this ->

driver function

memoized recursive solution

time complexity of this will be : O(N * N) -> as now my overlapping subproblems will only be computer once.

But here’s something that’s bugging me, in memoized solution the space complexity will be an extra space of O(N) apart from O(N*N) for the dp array. But that can be removed by converting this memoized(or top down) dp solution to tabulated(or bottom up) dp solution.

A bottom up dp solution will look something like this ->

bottom up dp

Here the base case will be pre-defined, as the entire array is already initialized to 0.

That’s it for today, hasta-la-vista baby!!