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

    static func kadane(_ a: [Int]) -> Int {
        var S = a[0]
        var S_end = a[0]
        let n = a.count-1

        for i in 1 ... 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
            }
        }
        return S
    }

    static func kadane2(_ a: [Int]) -> (Int, Int) {
        var S = a[0]
        var S_end = a[0]
        let n = a.count-1
        var l = 0
        var r = 0
        var l_end = 0

        for i in 1 ... 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
            }
        }
        return (l, r)
    }

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

    static func run() {
        print(kadane(a)) // 3
        print(kadane2(a)) // (2,8)
    }

}