# Lazy recursive solution support infinite houses like Fibonacci numbers

• 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)``````

• 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)))``

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