Lazy recursive solution support infinite houses like Fibonacci numbers


  • 3
    L

    For any non-negative infinite sequence X = {x[1], x[2], ....}, denote m[i] as the max sum of non-adjacent elements till x[i], say:
    m[i] is the max-sum of {x[1], x[2], ...., x[i]} without any adjacent elements.

    Specially, m[0] is max-sum of empty list, we have two trivial cases:

      m[0] = 0, m[1] = x[1]
    

    For any i > 1, we have the recursive case:

    m[i] = max (x[i] + m[i-2]) and m[i-1]
    

    This remind us the famous Fibonacci infinite definition:

    F = 0, 1, zip(+, F, F')
    

    This equation can be explained as the following table:

      F : 0, 1, 1, 2, 3, 5 , 8 , ...
      F': 1, 1, 2, 3, 5, 8 , 13, ...
    zip+: 1, 2, 3, 5, 8, 13, 21, ...
    

    We can do the same job with this problem. Put all m[i] together, we have an infinite list as M = {m[0], ,m[1], m[2], ....}, Removing the first m[0], denote the rest as M' = {m[1], m[2], m[3], ...}, we can draw a table like the following:

    X:        x[1], x[2], x[3], ...
    M:     0, x[1], m[2], ....
    M': x[1], m[2], m[3], ...
    

    And here is the recursive definition of the infinite sequence M:

    M = 0, x[1], zip(lambda(x', m, m') => max(x'+m, m'), X', M, M')
    

    Translate it into Haskell, we have the following implementation:

    maxsums [] = [0]
    maxsums [x] = [0, x]
    maxsums (x:xs) = ms where
      ms = 0 : x : zipWith3 (\x' m m' -> max (x' + m) m') xs ms (tail ms)
    

    We can easily verify the result with the imperative solution:

    maxsum2 xs = max a b where
      (a, b) = foldl (\(i, e) x -> (x + e, max i e)) (0, 0) xs
    
    prop_maxsums :: [Int] -> Bool
    prop_maxsums xs = let ns = map (abs . (`mod` 1000)) xs in maxsum2 ns == (last $ maxsums ns)

  • 0
    L

    As a reference, here is the equivalent 1 line python imperative solution with folding:

    return max(reduce(lambda (i, e), n: (n + e, max(i, e)), num, (0, 0)))

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.