def max_sum(arr)
	return (arr+[0]).max if arr.size < 3
 
	i=2
	curr_max = []
	curr_max[0] = (arr[0..0]+[0]).max
	curr_max[1] = (arr[0..1]+[0]).max
 
	while i<arr.size
		curr_max[i] = [arr[i] + curr_max[i-2], curr_max[i-1]].max
		i+=1
	end
	curr_max.last
end
 
puts max_sum([])
puts max_sum([-1, -2])
puts max_sum([5, 1, 1, 5])
puts max_sum([2, 0, 4, -2, -3, 0, 6, 2, 5])
puts max_sum([-1, -1, 2, 0, 4, -2, -3, 0, 6, 2, 5])
puts max_sum([0, 3, 4, 3, 0])

ZGVmIG1heF9zdW0oYXJyKQoJcmV0dXJuIChhcnIrWzBdKS5tYXggaWYgYXJyLnNpemUgPCAzCgoJaT0yCgljdXJyX21heCA9IFtdCgljdXJyX21heFswXSA9IChhcnJbMC4uMF0rWzBdKS5tYXgKCWN1cnJfbWF4WzFdID0gKGFyclswLi4xXStbMF0pLm1heAoKCXdoaWxlIGk8YXJyLnNpemUKCQljdXJyX21heFtpXSA9IFthcnJbaV0gKyBjdXJyX21heFtpLTJdLCBjdXJyX21heFtpLTFdXS5tYXgKCQlpKz0xCgllbmQKCWN1cnJfbWF4Lmxhc3QKZW5kCgpwdXRzIG1heF9zdW0oW10pCnB1dHMgbWF4X3N1bShbLTEsIC0yXSkKcHV0cyBtYXhfc3VtKFs1LCAxLCAxLCA1XSkKcHV0cyBtYXhfc3VtKFsyLCAwLCA0LCAtMiwgLTMsIDAsIDYsIDIsIDVdKQpwdXRzIG1heF9zdW0oWy0xLCAtMSwgMiwgMCwgNCwgLTIsIC0zLCAwLCA2LCAyLCA1XSkKcHV0cyBtYXhfc3VtKFswLCAzLCA0LCAzLCAwXSk=