Following on from EPI 6.3, we have three generalized versions of max difference:
Problem 1. Compute the maximum value of (A[j0] – A[i0]) + (A[j1] – A[i1]) such that i0 < j0 < i1 < j1.
The simple solution is O(n^4), by iterating all combinations of i0, j0, ii1 and ji1.
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[jt] – A[it]) for t = 0 -> k-1, such that i0 < j0 < i1 < j1 < … ik – 1 < jk – 1, for a fixed k.
Problem 3. Repeat (3) where k is any value between 0 and floor(n / 2).