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

  def maxsubSumInc(a: Array[Int]): Int = {
    var max = Int.MinValue
    for (l <- 0 until a.length) {
      var sum = 0
      for (r <- l until a.length) {
        sum = sum + a(r)
        if (sum > max) {
          max = sum
        }
      }
    }
    max
  }

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

  println(maxsubSumInc(a)) // 25

}