scala dfs recursion and memoization. and trampoline to avoid SO, thanks to broken jvm stack settings
scala dfs recursion and memoization.\nwe use trampoline to avoid SO, thanks to broken jvm stack settings\nscala\nobject Solution {\n  import scala.util.chaining
scala dfs recursion and memoization.\nwe use trampoline to avoid SO, thanks to broken jvm stack settings\n```scala\nobject Solution {\n  import scala.util.chaining._\n  import scala.util.control.TailCalls._\n  def maxOperations(nums: Array[Int]): Int = {\n\n    import scala.util.chaining._\n    import scala.util.control.TailCalls._\n    val cache = collection.mutable.Map.empty[(Int,Int,Int),TailRec[Int]]\n\n    def g1(sum: Int, l:Int,r:Int):TailRec[Int] = {\n      cache.getOrElse((sum,l,r), \n      (if (r-l<1) done(0.tap(rc => cache += ((sum,l,r) -> done(rc)))) else\n        for {\n          l2 <- if(nums(l) + nums(l+1) == sum) tailcall(g1(sum, l + 2, r)) else done(-1)\n          r2 <- if(nums(r) + nums(r-1) == sum) tailcall(g1(sum, l, r - 2)) else done(-1)\n          lr <- if(nums(l) + nums(r) == sum) tailcall(g1(sum, l + 1, r - 1)) else done(-1)\n        } yield {\n          (1 + (l2 max r2 max lr)).tap(rc => cache += ((sum,l,r) -> done(rc)))\n        }))\n    }\n    val ans = List(\n      g1(nums(0)+nums(1),2,nums.length-1).result,\n      g1(nums(nums.length-1)+nums(nums.length-2),0,nums.length-3).result,\n      g1(nums(0)+nums(nums.length-1),1,nums.length-2).result\n    ).maxOption.getOrElse(0)+1\n    ans\n\n  }\n\n\n  def maxOperationsDfs(nums: Array[Int]): Int =\n    import scala.util.chaining._\n    val cache = collection.mutable.Map.empty[(Int,Int,Int),Int]\n    def f(sum: Int, l:Int,r:Int):Int = cache.getOrElse((sum,l,r),\n      (if(r-l<1) 0 else List(\n          Option.when(nums(l) + nums(l+1) == sum){1+f(sum,l+2,r)},\n          Option.when(nums(r) + nums(r-1) == sum){1+f(sum,l,r-2)},\n          Option.when(nums(l) + nums(r) == sum){1+f(sum,l+1,r-1)}\n        ).flatten.maxOption.getOrElse(0)\n      ).tap(rc => cache += ((sum,l,r) -> rc)))\n    List(\n      f(nums(0)+nums(1),2,nums.length-1),\n      f(nums(nums.length-1)+nums(nums.length-2),0,nums.length-3),\n      f(nums(0)+nums(nums.length-1),1,nums.length-2)\n    ).maxOption.getOrElse(0)+1\n}\n```
['Scala']