Following on from EPI 6.3, we have three generalized versions of max difference:

**Problem 1. Compute the maximum value of (A[j**_{0}] – A[i_{0}]) + (A[j_{1}] – A[i_{1}]) such that i_{0} < j_{0} < i_{1} < j_{1}.

The simple solution is O(n^4), by iterating all combinations of i_{0}, j_{0}, ii_{1} and ji_{1}.

This could be improved to be O(n^2) by applying the O(n) solution to each entry in the array.

A O(n) solution with O(n) space is to compute the best solution in the forward and reverse directions (similar to max_increase_from_index in EPI 6.3) and use the two values on conjunction. This is:

max_increase_forward :: (Num a, Ord a) => [a] -> [(Integer, a, a)]
max_increase_forward [] = []
max_increase_forward (x:xs) = max_increase_forward' 0 (0,x) (x:xs)
where
max_increase_forward' i curr_max [] = []
max_increase_forward' i (j,aj) (x:xs)
| x >= aj = (j,aj,x - aj) : (max_increase_forward' (i + 1) (j,aj) xs)
| otherwise = (i,x,0) : (max_increase_forward' (i + 1) (i,x) xs)
max_increase_backward :: (Num a, Ord a) => [a] -> [(Integer, a, a)]
max_increase_backward xs = max_increase_backward' 0 xs
max_increase_backward' i [] = []
max_increase_backward' i [x] = [(i,x,0)]
max_increase_backward' i (x:xs)
| x <= aj = (j,aj,aj - x) : rest
| otherwise = (i,x,0) : rest
where
rest = max_increase_backward' (i + 1) xs
(j,aj,diff) = head rest

Now it is a matter of iterating the two results to find the maximum – done in O(n):

max_increase_k2 :: (Num a, Ord a) => [a] -> a
max_increase_k2 xs = maximumBy compare (max_increase_k2_iter fs rs)
where
fs = drop 1 (take (length xs - 1) (max_increase_forward xs))
rs = drop 2 (max_increase_backward xs)
max_increase_k2_iter [] [] = []
max_increase_k2_iter ((a1,a2,a3):fs) ((b1,b2,b3):rs) = (a3 + b3) : (max_increase_k2_iter fs rs)

**Problem 2. Compute maximum value of Sum(A[j**_{t}] – A[i_{t}]) for t = 0 -> k-1, such that i_{0} < j_{0} < i_{1} < j_{1} < … i_{k – 1} < j_{k – 1}, for a fixed k.

TBD

**Problem 3. Repeat (3) where k is any value between 0 and floor(n / 2).**

TBD

### Like this:

Like Loading...

*Related*

[…] EPI 6.4 – Generalized Max Difference […]