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
 */

object AuD_13_03_MaxSumArray_App extends App {

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

  def maxEndSum(a: Array[Int], n: Int): Int =
    if (n == 1)
      a(0)
    else
      Math.max(a(n-1), maxEndSum(a, n-1) + a(n-1))

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

  println(maxSum(a, a.length)) // 25

}