Analyse de la fonction max\_sous\_tableau

On considère le problème du sous-tableau maximal : trouver la somme maximale d'une sous-liste contiguë dans une liste de nombres (qui peuvent être négatifs). Comparer les deux fonctions suivantes :

def max_sous_tableau_naif(L):
    n = len(L)
    max_somme = float('-inf')
    for i in range(n):
        for j in range(i, n):
            somme = sum(L[i:j+1])
            if somme > max_somme:
                max_somme = somme
    return max_somme

def max_sous_tableau_kadane(L):
    max_global = max_courant = L[0]
    for x in L[1:]:
        max_courant = max(x, max_courant + x)
        max_global = max(max_global, max_courant)
    return max_global