algorithm - 将此算法转换为不使用递归的过程

Question

几周前我有一个任务要完成，我的思路是正确的，但是我当时给出的实现很糟糕。我有机会获得一些分数，但前提是我提供了正确的实现。 问题是:

Consider a list of integers [x_1; x_2;...;x_n]. We'll call index i "a hole" if 1 < i < n, such as x_i < max(x_1,...,x_{i-1}) and x_i < max(x_{i+1},...,x_n). The depth of this hole is min(max(x_1,...,x_{i-1})-x_i, max(x_{i+1},...,x_n)-x_i).

Write procedure hole : int list -> int which for given list of integers find the max depth on this list. If there is no hole on the list, then the correct answer is 0. For example: hole [5;2;7;10;3;7] = 3, because for i=2, max on the left is 5, max on the right is 10, min (5 - 2, 10-2) = 3. hole [1;2;3;2;1] = 0, because there is no such index i, that matches our predicate.

现在，我的过程看起来像这样使用递归:

let hole list =
   let rec aux maxL acc = function
    | [] -> (min_int, [])
    | x::xs ->
        let newMax = max maxL x in
        let (maxR, aclist) = aux newMax acc xs
        in
            if maxL > x && x < maxR then (max maxR x,(min (maxL-x) (maxR-x))::aclist)
            else (max maxR x, aclist)
in fold_left max 0 (snd (aux min_int [] list))

但我必须在不使用递归的情况下实现它，同时我能够使用高阶函数。 我想使用一种叫做“函数累积”的东西，但我不知道该怎么做(我已经考虑这个问题 7 个多小时了)。

欢迎使用 Haskell/OCaml 中给出的任何代码。唯一的问题是您不能使用递归。

Answer 1

这里的代码可以完成我认为您正在寻找的事情，即根据您对“洞”的描述，找到整数列表中最深“洞”的深度。它使用“中间”值的列表向上左右扫描最大值，如果需要，可以用“累积”一词来描述。

我敢肯定，这不是最有效的实现方式，但我认为它比明显的蛮力解决方案要好。如果没有找到洞，则返回 Nothing。

deepestHole' :: [Int] -> Maybe Int
deepestHole' xs 
  | length xs < 3 = Nothing
  | maxHole < 1 = Nothing
  | otherwise = Just maxHole
  where
    lMaxes = scanl1 max $ take (length xs - 2) xs
    rMaxes = scanr1 max (drop 2 xs)
    middles = tail $ init xs
    holeDepth lMax mid rMax = min lMax rMax - mid
    maxHole = maximum $ zipWith3 holeDepth lMaxes middles rMaxes