dynamic programming

def maxSumNoAdjacent(a: Array[Int]): Int = {
  def best(i: Int): Int = {
    if(i >= a.length) 0
    else (a(i) + best(i+2)) max best(i+1)
  }
  best(0)

  /////
  val best = Array.fill(a.length+2)(-99)
  for(i <- best.indices.reverse) {
    best(i) = {
      if(i >= a.length) 0
      else (a(i) + best(i+2)) max best(i+1)
    }
  }
  best(0)
}

=====

def lis(a: Array[Int]): Int = {
  // best(i) is the length of the lis that actively starts at index i
  // def best(i: Int): Int = {
  val best = Array.fill(a.length)(-99)
  for(i <- a.indices.reverse) {
    best(i) = {
      if( (i+1 to a.length).forall(j => a(j) <= a(i)) ) 1
      else 1 + (i+1 to a.length).filter(j => a(j) > a(i)).map(best(_)).max
    }
  }
  //best(i)
  best.max
}