Array ,question 6.4 (finding maximum value (a[i]-a[j])+(a[i-1])-a[j-1])+..(a[i-k]-a[j-k]) )

#1

I understood the explanation about forward iteration and reverse iteration and able to think solution of this problem
1)Compute the maximum value of (A[j0l - A[i0)) + (A[j1l - A[i1), subject to i0 < j0 <
i1 < j1
but when it is generalised up to given K times(given) ,I am not able to understand the solution,the explanation given in the book is::

Define B(i,j) to be the most money you can have if you must make
j - 1 buy-sell transactions prior to i and buy at i. Define S(i,j) to be the maximum profit
achievable with j buys and sells with the j-th sell taking place at i.

0 Likes
#2

Hey @ankit,

It is a very hard problem, and I find the easier way to understand this is to treat the S(i,j) function as a temporary storage that we try to cache the intermediate computation to solve this problem by DP.

0 Likes