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
Pk1
t=0 (A[jt] A[it]), subject to i0 < j0 < i1 < j1 <
< ik1 < jk1. 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