exercices corrigés sur les tableaux -TD3-

def MoyenneSousTab(tab, n, x, y):
    """
    Trouve la moyenne maximale d'un sous-tableau de taille entre x et y
    
    Paramètres:
        tab: tableau d'entrée
        n: taille du tableau
        x: taille minimale du sous-tableau
        y: taille maximale du sous-tableau
    """
    # calculer la somme cumulative (préfixe)
    cumule = [0] * n
    cumule[0] = tab[0]
    for i in range(1, n):
        cumule[i] = cumule[i - 1] + tab[i]

    maximum = 0

    # parcourir tous les sous-tableaux
    for i in range(n):
        j = i + x - 1  # premier sous-tableau de taille x commençant à i

        # sous-tableaux de taille de X à Y
        while j < i + y and j < n:

            # récupérer la somme du sous-tableau
            somme = cumule[j]
            if i > 0:
                somme -= cumule[i - 1]

            # calculer la moyenne
            moyenneCourante = somme / (j - i + 1)

            # stocker le maximum
            maximum = max(maximum, moyenneCourante)

            j += 1
            
    return maximum


# Test
T = [1, 2, 3, 4, 5]
X = 2
Y = 3

print(f"Moyenne maximale pour {T} avec X={X}, Y={Y}:")
print(MoyenneSousTab(T, len(T), X, Y))

def equilibre_naif(tab, n):
    """
    Trouve le plus grand sous-tableau avec autant de 0 que de 1
    Version naïve - O(n²)
    """
    somme = 0
    max_taille = -1
    debut = -1
    
    for i in range(0, n):
        # Convertir 0 en -1 pour faciliter le calcul
        somme = -1 if (tab[i] == 0) else 1

        # parcourir les sous-tableaux à partir de i
        for j in range(i + 1, n):
            # mettre à jour la somme
            if tab[j] == 0:
                somme += -1
            else:
                somme += 1

            # Si somme devient 0, on a autant de 0 que de 1
            if somme == 0 and max_taille < j - i + 1:
                max_taille = j - i + 1
                debut = i

    if max_taille == -1:
        print("Aucun sous-tableau trouvé")
        return -1
    else:
        print(f"Plus grand sous-tableau de {debut} à {debut + max_taille - 1}")
        return max_taille


# Test
T = [0, 0, 1, 1, 0]
print("Test avec [0, 0, 1, 1, 0] :")
equilibre_naif(T, len(T))

def equilibre_optimale(tab, n):
    """
    Trouve le plus grand sous-tableau avec autant de 0 que de 1
    Version optimisée - O(n) avec table de hachage
    """
    # Remplacer 0 par -1
    for i in range(n):
        if tab[i] == 0:
            tab[i] = -1

    # Dictionnaire pour stocker la première occurrence de chaque somme
    # La clé est la somme, la valeur est l'index
    hash_map = {}

    somme = 0
    max_taille = 0
    fin = -1

    for i in range(n):
        somme += tab[i]

        # Si la somme est 0, le sous-tableau de 0 à i a autant de 0 que de 1
        if somme == 0:
            max_taille = i + 1
            fin = i

        # Si la somme a déjà été vue, le sous-tableau entre la première occurrence
        # et l'index actuel a une somme de 0
        if somme in hash_map:
            if max_taille < i - hash_map[somme]:
                max_taille = i - hash_map[somme]
                fin = i
        else:
            # Première occurrence de cette somme
            hash_map[somme] = i

    if max_taille == 0:
        print("Aucun sous-tableau trouvé")
        return 0
    else:
        debut = fin - max_taille + 1
        print(f"Plus grand sous-tableau de {debut} à {fin}")
        return max_taille


# Test avec les exemples
print("Exemple 1: [1, 0, 1, 1, 1, 0, 0]")
T1 = [1, 0, 1, 1, 1, 0, 0]
equilibre_optimale(T1, len(T1))

print("\nExemple 2: [0, 0, 1, 1, 0]")
T2 = [0, 0, 1, 1, 0]
equilibre_optimale(T2, len(T2))