dynamic programming - 2 shot strategy and kshot strategy algorithm for selling stocks -

the classic maximize stock profit questions involves array stock prices , required return max profit can made:

i understand logic maximizing profit given stock quotes. in simple way, can maintain running min , running max_so_far , check if current elem less min or current elem - running min greater max_so_far , if yes, update our max_so_far

we return our max_so_far maximum profit can made.

now, how solve problem 2 shot strategy? required return i0, j0, i1, j1 such sum of arr[j0]-arr[i0] , arr[j1]-arr[i1] maximum , i0<j0 < i1 <j1

i able think extent couldnt figure out later how generalize it. so, 1st single shot solution array containing max_so_far elems. similarly, similar array starting arr[n-1] 0. tells me if have sell after today, max profit can make. if add corresponding elements in array in forward iteration , array in backward iteration , max element out of it, corresponds max i0,j0,i1,j1

but can first explain logic k shot algorithm. guess i'll want understand k-shot strategy how can extend 2 shot strategy k shot.

thanks

one generalization keep 2k+1 element array j^th entry (counting zero) maximum cash on hand after j transactions alternately buying , selling. if j even, next transaction buy. if j odd, next transaction sell.

initially, array 0, -inf, -inf, ..., -inf (negative infinity means entry infeasible). when next price p comes in, update elements @ indices 2k, 2k-1, ..., 1 in order follows. best transaction 2k max of (i) previous entry, signifying 2k previous transactions (ii) entry 2k-1 plus p, signifying 2k-1 previous transactions followed selling @ p. best transaction 2k-1 max of (i) previous entry, signifying 2k-1 previous transactions (ii) entry 2k-2 minus p, signifying 2k-2 previous transactions followed buying @ p. continue alternate plus , minus.

i'll leave problem of recovering buy/sell timing exercise.