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_13_KadaneDP_App extends App { def kadane(a: Array[Int]): Int = { var S = a(0) var S_end = a(0) val n = a.length-1 for (i <- 1 to n) { if (S_end + a(i) >= a(i)) { S_end = S_end + a(i) } else { S_end = a(i) } if (S_end > S) { S = S_end } } S } def kadane2(a: Array[Int]): (Int, Int) = { var S = a(0) var S_end = a(0) val n = a.length-1 var l = 0 var r = 0 var l_end = 0 for (i <- 1 to n) { if (S_end + a(i) >= a(i)) { S_end = S_end + a(i) } else { S_end = a(i) l_end = i } if (S_end > S) { S = S_end l = l_end r = i } } (l, r) } val a = Array(1, -4, 3, 18, 1, -8, 2, -1, 10, -5, -80, 20, 3, -2) println(kadane(a)) // 25 println(kadane2(a)) // 25 }