# sous-tableau de somme maximale
#
# étant donné un tableau d'entiers, on cherche la somme maximale
# obtenue en ajoutant des éléments consécutifs de ce tableau
#
# ainsi, dans le tableau [2, -7, 4, 3, -1, 5, -2]
# la somme maximale est 11, obtenue pour [4, 3, -1, 5]
#
# si le tableau ne contient que des entiers négatifs,
# la réponse est 0

def stm1(t):
    n = len(t)
    ms = 0 # la meilleure somme trouvée
    for g in range(n):
        for d in range(g, n):
            # on calcule la somme de t[g..d]
            s = 0
            for i in range(g, d+1):
                s += t[i]
            if s > ms:
                ms = s
    return ms

t = [2, -7, 4, 3, -1, 5, -2]
assert stm1(t) == 11
neg = [-7, -3, -1, -11]
assert stm1(neg) == 0

def stm2(t):
    n = len(t)
    ms = 0 # la meilleure somme trouvée
    for g in range(n):
        s = 0
        for d in range(g, n):
            # invariant s = la somme de t[g..d-1]
            s += t[d]
            if s > ms:
                ms = s
    return ms

assert stm2(t) == 11
assert stm2(neg) == 0


def stm3rec(t, g, d):
    """renvoie la somme maximale pour t[g..d]"""
    if d < g: return 0
    assert 0 <= g and d < len(t)
    m = g + (d - g) // 2
    ms = 0 # la meilleure somme trouvée
    s = 0
    for i in range(m - 1, g - 1, -1):
        s += t[i]
        if s > ms:
            ms = s
    s = ms
    for i in range(m, d + 1):
        s += t[i]
        if s > ms:
            ms = s
    sgauche = stm3rec(t, g, m - 1)
    if sgauche > ms:
        ms = sgauche
    sdroite = stm3rec(t, m + 1, d)
    if sdroite > ms:
        ms = sdroite
    return ms

def stm3(t):
    return stm3rec(t, 0, len(t) - 1)

assert stm3(t) == 11
assert stm3(neg) == 0

# algorithme de Kadane

def stm4(t):
    n = len(t)
    ms = 0 # la meilleure somme trouvée
    s = 0
    for i in range(0, n):
        if s < 0:
            s = t[i]
        else:
            s += t[i]
        if s > ms:
            ms = s
    return ms

assert stm4(t) == 11
assert stm4(neg) == 0