Problème — Sous-tableau de somme maximale

on coupe le tableau au milieu. La somme maximale est soit entièrement à gauche, soit entièrement à droite, soit à cheval sur le milieu. Ce dernier cas se calcule en partant du milieu vers la gauche puis vers la droite.

def somme_centre(tab, g, m, d):
    # meilleure somme finissant en m (cote gauche)
    s, gauche = 0, float("-inf")
    for k in range(m, g - 1, -1):
        s += tab[k]
        gauche = max(gauche, s)
    # meilleure somme commencant en m+1 (cote droit)
    s, droite = 0, float("-inf")
    for k in range(m + 1, d + 1):
        s += tab[k]
        droite = max(droite, s)
    return gauche + droite

def somme_max(tab, g, d):
    if g == d:                       # cas de base
        return tab[g]
    m = (g + d) // 2
    return max(somme_max(tab, g, m),
               somme_max(tab, m + 1, d),
               somme_centre(tab, g, m, d))

def sous_tableau_max(tab):
    return somme_max(tab, 0, len(tab) - 1)

La complexité est $O(n\log n)$, contre $O(n^2)$ pour l'approche naïve qui testerait tous les sous-tableaux. (L'algorithme de Kadane fait même $O(n)$, mais n'utilise pas le paradigme étudié ici.)