exercices corrigés sur les tableaux -TD3-

                def MoyenneSousTab(tab, n, x, y):

                    # calculer la somme cumulative
                    cumule = [0] * n
                    cumule[0] = tab[0]
                    for i in range(1, n):
                        cumule[i] = cumule[i - 1] + tab[i]
                
                    maximum = 0
                
                    # parcourir les sous tableaux
                    for i in range(n):
                        j = i + x - 1
                
                        # sous tableau de taille [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
                
                
                T = [1, 2, 3, 4, 5]
                X = 2
                Y = 3
                
                print(MoyenneSousTab(T, len(T), X, Y))
            

def SameZeroOne(tab, n):

    somme = 0
    fin = -1
    for i in range(0, n-1):
        somme = -1 if (tab[i] == 0) else 1

        # parcourir les sous tableaux
        for j in range(i + 1, n):

            somme = somme + (-1) if (tab[j] == 0) else somme + 1

            # Si somme devient 0, alors la taille de ce sous-tableau est comparée
            # à la plus grande taille jusqu'à présent.
            if (somme == 0 and fin < j-i + 1):
                fin = j - i + 1
                debut = i

    if (fin == -1):
        print("tableau n'exist pas")
    else:
        print(debut, " à ", debut + fin-1)

    return fin


T = [0, 0, 1, 1, 0]
SameZeroOne(T, len(T))

            

Soit un tableau en entrée de taille n et max_taille est la taille de sous-tableau en sortie.

1. Considérons toutes les valeurs 0 comme -1. Le problème se réduit maintenant pour trouver la longueur maximale du sous-tableau avec somme = 0.
2. Créez un tableau temporaire sommeleft[] de taille n. Stocke la somme de tous les éléments de tab [0] à tab [i] dans sommeleft [i]. Cela peut être fait en un temps O (n).
3. Il existe deux cas, le sous-tableau de sortie peut commencer à partir d'index 0 ou peut-être à partir d'un autre index. Nous renverrons le maximum des valeurs obtenues par ces deux cas.
4. Pour trouver la longueur maximale du sous-tableau à partir d'index 0, parcourir sommeleft[] et recherchez le maximum i où sommeleft[i] = 0.
5. Maintenant, nous devons trouver le sous-tableau où somme est 0 et index début n'est pas 0.
   Ce problème revient à trouver deux indices i & j dans sommeleft[] tels que sommeleft[i] = sommeleft[j] et j-i est maximum.
   Pour résoudre ce problème, nous pouvons créer une table de hachage de taille=max-min + 1 où min est la valeur minimale dans le sommeleft[] et max est la valeur maximale dans sommeleft[].
   L'idée est de hacher les occurrences les plus à gauche de toutes les valeurs différentes dans sommeleft[]. La taille de hash est choisie comme max-min + 1 car il peut y avoir autant de valeurs possibles dans sommeleft[]. Initialise toutes les valeurs dans hash avec -1
6. Pour remplir et utiliser le hash[], traversez sommeleft[] de 0 à n-1. Si une valeur n'est pas présente dans hash[], stockez son index dans hash. Si la valeur est présente, calculez la différence entre l'index actuel de sommeleft[] et la valeur précédemment stockée dans hash[]. Si cette différence est supérieure à max_taille, mettez à jour max_taille.
7. Pour gérer les cas de coin (tous les 1 et tous les 0), nous initialisons max_taille à -1. Si la taille maximale reste égale à -1, affichez alors "ce sous-tableau n'existe pas".

                def SameZeroOne(tab, n):

                    # créer un tableau de hashage
                    #  ce tableau de hashage est implémenté à l'aide du dictionnaire en python
                    hash = {}
                
                    max_taille = 0
                
                    sommeLeft = []
                    max = min = tab[0]
                    sommeLeft.append((-1 if tab[0] == 0 else 1))
                
                    for i in range(1, n):
                        val = sommeLeft[i-1] + (-1 if tab[i] == 0 else 1)
                        sommeLeft.append(val)
                        if sommeLeft[i] < min:
                            min = sommeLeft[i]
                
                        if sommeLeft[i] > max:
                            max = sommeLeft[i]
                
                    # Initialiser le tableau de hashage avec -1
                    for i in range((max-min+1)):
                        hash[i] = -1
                
                    for i in range(n):
                        if sommeLeft[i] == 0:
                            max_taille = i+1
                            debut = 0
                
                        if hash[sommeLeft[i]-min] == -1:
                            hash[sommeLeft[i]-min] = i
                        else:
                            if (i-hash[sommeLeft[i]-min]) > max_taille:
                                max_taille = i-hash[sommeLeft[i]-min]
                                debut = hash[sommeLeft[i]-min]+1
                
                    if max_taille == -1:
                        print("sous tableau n'existe pas ")
                    else:
                        print(debut, " à ", debut+max_taille-1)
                
                    return max_taille
                
                
                T = [0, 0, 1, 1, 0]
                SameZeroOne(T, len(T))