Best Time to buy and sell stocks
So given an array with integers which represents the price of the stock at day i find the maximum profit that can be earned by buying and selling stocks
- Case 1 when you are allowed only a single transaction :
This means you have to find indexes with maximum difference . This can be easily solved by converting the problem in maximum contiguous sum problem
Just keep running through the array if prices[i] > prices[i-1] add the diff tot the running sum if running sum is greater than the current maximum sum update maximum sum to be equal to running sum if running sum becomes negative reset the running sum
2. Case 2 when you can do multiple transaction
This means you can buy and sell stocks multiple number of times . So whenever prices[i] > prices[i-1] add it to the running sum return this running sum at the end
3. Case 3 : when you can do k most transaction
This can be done by dynamic programming. Initialize a dp table with number of rows equal to k and number of cols equal to the length of the prices array
Now the dp table[i][j] will tell us the maximum profit that can be made on day j using at most i transaction
dptable[i][j] = max( dptable[i][j-1] , the maximum profit obtained without selling on day j , max(prices[j] — prices[k] + dptable[i-1][k] for k in range of 0 .. j-1)
Now this can be done in linear time by keeping a running maximum
Note that when you are at the second index of the array
according to the formula
dptable[i][1] = max(dptable[i][0],max( prices[1] — prices[0] + dptable[i-1][0] for k in range0 ..0))
so there is only one viable k in the beginning now rearranging the terms we can rewrite the previous equation as
dptable[i][1] = max(dptable[i][0] , max(prices[1] + dptable[i-1][0] — prices[0]))
now this bold part is the part that changes frequently for every index in the prices array
let the current value of this bold part be tempmax
now for index 2 the bold part is
max(prices[2] + dptable[i-1][0] — prices[0] , prices[2] +dptable[i-1][1] — prices[1])
or this can be rewritten as
max(tempmax, dptable[i-1][1] -prices[1]) + prices[2]
So after doing the calculation for index 1 we can update tempmax
as tempmax = max(tempmax, dptable[i-1][1] — prices[1])
and on next iteration just use
dptable[i][2] = max(dptable[i][1], prices[2] + tempmax)
if k ≥ n/2 we can do any number of transactions