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

    static func maxSumMem(_ a: [Int]) -> Int {
        var mem: [Int : Int] = [:]

        func maxSum(_ n: Int) -> Int {
            if n == 1 {
                return a[0]
            } else {
                return max(maxEndSum(n), maxSum(n - 1))
            }
        }

        func maxEndSum(_ n: Int) -> Int {
            mem[n]
                ?? ( n == 1 ? a[0]
                : { () in let res: Int = max(a[n - 1], maxEndSum(n - 1) + a[n - 1])
                    mem[n] = res
                    return res
                  }())
        }

        return maxSum(a.count)
    }

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

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

}