memoization

def maxSum(arr: Array[Int]): Int = {
  def maxFrom(index: Int): Int = {
    if(index >= arr.length) return 0
    else arr(index) + (maxFrom(index+2) max maxFrom(index+3))
  }
  maxFrom(0) max maxFrom(1)
}

===========

Memoization -- remembering answers that you've already seen

We can actually use a special data structure here; map where keys are consecutive integers starting with zero == an array

def maxSum(arr: Array[Int]): Int = {
  var memo = Array.fill(arr.length+2)(-99)
  def best(index: Int): Int = {
    if(memo(i) == -99) {
      memo(i) == {
        if(index >= arr.length) return 0
        else (a(i) + best(i+2)) max best(i+1)
      }
    }
    memo(i)
  }
  best(0)
}