please help me with recussive approach
Help me to develop recursive approachj for it
For recursive approach lets try to think of states first:
- Obviously we would have to iterate over the array, so we need a state i
State i: tells the index we are presently considering, range=[1,n]
- Now when standing on ‘i’ we would have to make a choice whether to buy a stock or sell the previous stock. As there can be no overlaps between transactions, so we need something to know that whether any previous transaction is pending and, if yes, what was its starting point. So we a state prev
State prev: tells the previous index where we bought a stock, (=-1 if no ongoing transaction),
range={-1,[1,n]}
- Also as we have a constraint of ‘k’ transactions only, we also need something to know how many transactions are already over, thus we need a state trans_cnt
State trans_cnt: tells the number of transactions already completed, range=[0,k].
Recursion would be:
Case 1: Already active transaction:
Here we have 2 choices, either we end the transaction here, or continue it further.
Case 2: No active transaction:
Here we have 2 choices, either start a new transaction or don’t and simply continue by skipping the current element. Also we can only start a new transaction if we haven’t already completed ‘k’ transactions.
Case 3: Base Case:
After reaching the end of the array, we can conclude by checking that we are not inside an active transaction and also that ‘k’ transactions are complete, if both are true we return 0, else we return -infinity.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.