Le problème de la somme maximale d'une sous-séquence consiste à identifier, au sein d'une suite de k entiers {N1, N2, ..., Nk}, la sous-chaîne contiguë dont la somme des éléments est la plus élevée. Par exemple, pour l'ensemble { -2, 11, -4, 13, -5, -2 }, la séquence optimale est { 11, -4, 13 }, totalisant 20. Par convention, si tous les nombres sont négatifs, le résultat retourné est 0.

1. Approche par force brute (Complexité : O(N³))

Cette méthode consiste à énumérer absolument toutes les combinaisons possibles de début et de fin de sous-séquences, puis à calculer manuellement la somme de chaque segment.

int SommeMaximale_Cube(const int tableau[], int taille) {
    int score_max = 0;
    for (int debut = 0; debut < taille; debut++) {
        for (int fin = debut; fin < taille; fin++) {
            int somme_segment = 0;
            for (int k = debut; k <= fin; k++) {
                somme_segment += tableau[k];
            }
            if (somme_segment > score_max) {
                score_max = somme_segment;
            }
        }
    }
    return score_max;
}

2. Optimiastion de la force brute (Complexité : O(N²))

L'inefficacité de l'algorithme précédent provient du recalcul répété des sommes. En observant que la somme d'un segment [i, j] est simplement la somme de [i, j-1] + tableau[j], nous pouvons supprimer la boucle la plus interne.

int SommeMaximale_Carre(const int tableau[], int n) {
    int score_max = 0;
    for (int i = 0; i < n; i++) {
        int cumul_local = 0;
        for (int j = i; j < n; j++) {
            cumul_local += tableau[j];
            if (cumul_local > score_max) {
                score_max = cumul_local;
            }
        }
    }
    return score_max;
}

3. Stratégie "Diviser pour Régner" (Complexité : O(N log N))

En utilisant la récursivité, nous divisons le tableau en deux. La sous-séquence maximale se trouve soit entièrement dans la moitié gauche, soit entièrement dans la moitié droite, soit elle chevauche le milieu. Pour le cas du chevauchement, on calcule la plus grande somme partant du centre vers la gauche et celle partant du centre vers la droite, puis on les adidtionne.

static int Max3(int a, int b, int c) {
    int max = (a > b) ? a : b;
    return (max > c) ? max : c;
}

int CalculRecursif(const int T[], int gauche, int droite) {
    if (gauche == droite) {
        return (T[gauche] > 0) ? T[gauche] : 0;
    }

    int milieu = (gauche + droite) / 2;
    int max_gauche = CalculRecursif(T, gauche, milieu);
    int max_droite = CalculRecursif(T, milieu + 1, droite);

    int somme_limite_gauche = 0, max_limite_gauche = 0;
    for (int i = milieu; i >= gauche; i--) {
        somme_limite_gauche += T[i];
        if (somme_limite_gauche > max_limite_gauche) max_limite_gauche = somme_limite_gauche;
    }

    int somme_limite_droite = 0, max_limite_droite = 0;
    for (int i = milieu + 1; i <= droite; i++) {
        somme_limite_droite += T[i];
        if (somme_limite_droite > max_limite_droite) max_limite_droite = somme_limite_droite;
    }

    return Max3(max_gauche, max_droite, max_limite_gauche + max_limite_droite);
}

4. Algorithme de Kadane / Programmation Dynamique (Complexité : O(N))

C'est l'approche la plus performante. On parcourt le tableau une seule fois. À chaque étape, on ajoute l'élément courant à une somme temporaire. Si cette somme devient négative, elle ne peut plus contribuer à augmenter une future séquence, on la réinitialise donc à zéro. À chaque itération, on met à jour la valeur maximale rencontrée.

int SommeMaximale_Lineaire(const int entiers[], int nb_elements) {
    int cumul_actuel = 0;
    int meilleur_total = 0;

    for (int i = 0; i < nb_elements; i++) {
        cumul_actuel += entiers[i];

        if (cumul_actuel > meilleur_total) {
            meilleur_total = cumul_actuel;
        } else if (cumul_actuel < 0) {
            cumul_actuel = 0;
        }
    }
    return meilleur_total;
}

Cette méthode, souvent appelée "algorithme en ligne", est optimale car elle ne nécessite qu'un seul passage sur les données et utilise un espace mémoire constant.