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

struct AuD_13_06_MaxSumGrowing {

    static func maxSumGrowing(_ a: [Int]) -> Int {
        var maxSum: [Int] = [Int](repeating: 0, count: a.count)
        var maxEndSum: [Int] = [Int](repeating: 0, count: a.count)
        let n = a.count-1

        maxSum[0] = a[0]
        maxEndSum[0] = a[0]

        for i in 1 ... n {
            maxEndSum[i] = max(a[i], maxEndSum[i-1] + a[i])
            maxSum[i] = max(maxEndSum[i], maxSum[i-1])
        }

        return maxSum[n]
    }

    static let a = [1, -4, 3, 18, 1, -8, 2, -1, 10, -5, -80, 20, 3, -2]

    static func run () {
        print(maxSumGrowing(a)) // 25
    }
}