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

    static func maxSum(_ lst: [Int]) -> Int {
        if lst.count == 0 {
            return 0
        } else if lst.count == 1 {
            return lst[0]
        } else {
            let tail = Array(lst.dropFirst())
            return max(maxEndSum(lst), maxSum(tail))
        }
    }

    static func maxEndSum(_ lst: [Int]) -> Int {
        if lst.count == 1 {
            return lst[0]
        } else {
            let head = lst[0]
            let tail = Array(lst.dropFirst())
            return max(head, maxEndSum(tail)+head)
        }
    }

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

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

}