package kapitel_13

/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 13, Dynamisches Programmieren
 *
 * @author A. Gogol-Döring, Th. Letschert
 */

import scala.collection.mutable

object AuD_13_05_MaxSumMem_App extends App {

  def maxSumMem(a: Array[Int]): Int = {

    val mem: mutable.HashMap[Int, Int] = mutable.HashMap()

    def maxSum(n: Int): Int = {
      if (n == 1)
        a(0)
      else
        Math.max(
          maxEndSum(n),
          maxSum(n - 1)
        )
    }

    def maxEndSum(n: Int): Int =
      mem.getOrElse(n, {
        if (n == 1)
          a(0)
        else {
          val res = Math.max(a(n - 1), maxEndSum(n - 1) + a(n - 1))
          mem.update(n, res)
          res
        }
      })

    maxSum(a.length)
  }

  val a = Array(1, -4, 3, 18, 1, -8, 2, -1, 10, -5, -80, 20, 3, -2)

  println(maxSumMem(a)) // 25

}