Stock selling - DP

#1

not getting how to approach this problem .

#2

@Vishal123 hi,the problem can be solved by using dynamic programming.Here is recurrence relation:
Let profit[t][i] represent maximum profit using at most t transactions up to day i (including day i). Then the relation is:

profit[t][i] = max(profit[t][i-1], max(price[i] – price[j] + profit[t-1][j]))
for all j in range [0, i-1]

profit[t][i] will be maximum of –

profit[t][i-1] which represents not doing any transaction on the ith day.
Maximum profit gained by selling on ith day. In order to sell shares on ith day, we need to purchase it on any one of [0, i – 1] days. If we buy shares on jth day and sell it on ith day, max profit will be price[i] – price[j] + profit[t-1][j] where j varies from 0 to i-1. Here profit[t-1][j] is best we could have done with one less transaction till jth day.

#3

not unable to understand what profit[t-1][j] represents

#4

@Vishal123 profit[t-1][j] is best profit which can be made till current transaction -1 mtlb ek kam transaction se till jth day.Ek bar dry run krke dekho you will get it.