Problem 6.3 ,epi-1.4.4

#1

For each of the following, A is an integer array of length n
(1.) Compute the maximum value of (A[j0] 􀀀 A[i0]) + (A[j1] 􀀀 A[i1]), subject to i0 < j0 <
i1 < j1.
(2.) Compute the maximum value of
Pk􀀀1
t=0 (A[jt] 􀀀 A[it]), subject to i0 < j0 < i1 < j1 <
< ik􀀀1 < jk􀀀1. Here k is a fixed input parameter.
(3.) Repeat Problem (2.) when k can be chosen to be any value from 0 to bn=2c.

Answer Given :
performing a forward iteration and storing the best solution for A[0 : j]; 1<=j<= n-1. We then do
a reverse iteration, computing the best solution for A[j : n-􀀀1]; j belongs to [0; n-􀀀2], which we
combine with the result from the forward iteration.

I am not able to understand this ,Explanation with examples will be a great help,
Thanks,
Ankit

0 Likes

#2

Hey @ankit,

Sorry for your confusion, and we have tried to rewrite this problem in the later edition. If you haven’t figured it out, please take a look of this https://www.youtube.com/watch?v=oDhu5uGq_ic

0 Likes