gistfile1.py

# rob houses (3,5,1,7,9) where the rule is
# you can not rob adjacent houses and the goal
# is to get the maximum sum value

# 3 => 3
# 3, 5 => 5
# 3, 5, 1 => 5
# 3, 5, 1, 7 => 12
# ...
# 3, 5, 1, 7, 9
#   either 3517 + 9 or
#          351 + 9, where:
#   3517 + 9 is discarded because 7 and 9 are adjacent
#   so we take 351 + 9

def rob(xs):
    if not xs:
        return 0

    if len(xs) == 1:
        return xs[0]

    if len(xs) == 2:
        return max(xs[0], xs[1])

    results = []
    for i, x in enumerate(xs):
        include = rob(xs[i:-2]) + xs[-1]
        exclude = rob(xs[i:-1])
        results.append(max(include, exclude))

    return max(results)

def test(actual, expected):
    if (actual != expected):
        print "[FAILED] actual: {}, expected: {}".format(actual, expected)

if __name__ == "__main__":
    test(rob([]), 0)
    test(rob([1]), 1)
    test(rob([1,2]), 2)                 # [2]
    test(rob([1,2,3]), 4)               # [1, 3]
    test(rob([3,5,1,7,9,6]), 18)        # [5, 7, 6]
    test(rob([9,9,9,9,9]), 27)          # [9, 9, 9]
    test(rob([-3,-2,-1,0,1,2,3]), 4)    # [1, 3]

    print "if you are seeing this message, done"