dynamic programming solution to robbers problem -- runs in linear time in the size of the array. tested against my previous brute force solution.

max_sum.rb

a = [447, 462, 9, 272, 242, 0, 206, 998, 35, 414]

def max(a, i, memo = {})
  return 0 if i == 0
  return a[i] if i == 1
  return memo[i] if memo[i]
  return memo[i] = [max(a,i-2) + a[i], max(a,i-1)].max
end

p max(a, 9)