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_06_MaxSumGrowing_App extends App {

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

    val maxSum: Array[Int] = Array.ofDim(a.length)
    val maxEndSum: Array[Int] = Array.ofDim(a.length)

    val n = a.length-1

    maxSum(0) = a(0)
    maxEndSum(0) = a(0)

    for (i <- 1 to n) {
      maxEndSum(i) = Math.max(a(i), maxEndSum(i-1) + a(i))
      maxSum(i) = Math.max(maxEndSum(i), maxSum(i-1))
    }

    maxSum(n)
  }

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

  println(maxSumGrowing(a)) // 25
}