Best Time to buy and sell stocks

Nitish Chandra
Aug 9, 2017 · 2 min read

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

  1. 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

Nitish Chandra

Written by

Software Engineer