Programming Elements 6.4 Strategy strategy of two shots and k-shots

Question

The search is difficult to understand shot strategy and k-shot algorithms. Here's another question:

Q1) arr is an array of length n. Calculate max A [j0] -A [i0] + A [j1] -A [i1] provided that i0 <j0 <i1 <j1

Ans) We can make a one-time (i.e. small sale income) in O (n). We can apply the same technique to find max from 0 .. j and max from j..n. That would be a solution to O (n2).

Elements of Programming interviews book suggests a way of doing this in O(n) time by: doing a forward iteration and storing solution for A[0:j] such that 1<=j<=n-1 and then a backward iteration for A[j:n-1] such that 0<=j<=n-2 and then combining the two results. Does anyone have any idea how this can be done? 

Q2) How do you do k-shot?

thanks!!

Answer 1

Q1

First solve this easier problem in O(n) : find i0 < j0 to maximize A[j0] - A[i0] .

For each j0 we need to find the minimum 0, 1, ..., j0 - 1 and compare A[j0] - this minimum with the global maximum. This is easy to do by simply calculating the minimum while we go.

Now for your original problem, we need i1 < j1 to maximize A[j1] - A[i1] . Or, for each i1 , we need to find j1 > i1 such that A[j1] - A[i1] maximized.

Let be:

 min[i] = minimum in [0, ..., i] max[i] = maximum in [i, ..., n - 1] 

So, now we need i < j such that A[i] - min[i - 1] + max[j + 1] - A[j] maximized. This can be done by computing in O(n) :

 max1[i] = max{A[1] - min[0], A[2] - min[1], ..., A[i] - min[i - 1]} max2[i] = max{max[i + 1] - A[i], max[i] - A[i - 1], ...max[1] - A[0]} 

Then just take max max1[i - 1] + max2[i] for all i >= 2 .