Comment Trouver la Sous-Séquence Croissante de Somme Maximale : Guide Complet et Exemples

Vous cherchez à optimiser vos algorithmes et impressionner vos collègues ? Découvrez comment identifier la sous-séquence croissante avec la somme la plus élevée dans un tableau. Ce guide simple vous fournira des explications claires et des exemples de code dans plusieurs langages.

Qu'est-ce qu'une Sous-Séquence Croissante de Somme Maximale ?

Il s'agit d'un problème classique d'algorithmique qui consiste à trouver, dans une séquence de nombres, une sous-séquence dont les éléments sont en ordre croissant et dont la somme est la plus grande possible. Une sous-séquence n'est pas forcément contiguë.

• Exemple Simple: Dans le tableau {1, 101, 2, 3, 100, 4, 5}, la sous-séquence croissante de somme maximale est {1, 2, 3, 100}, dont la somme est 106.

Pourquoi est-ce important ?

Comprendre cet algorithme est crucial parce qu'il illustre des concepts clés de la programmation dynamique, une technique puissante pour résoudre des problèmes d'optimisation. Il peut être appliqué dans divers domaines, comme l'analyse financière et la bio-informatique.

Approche de Programmation Dynamique : Une Solution Efficace

La solution utilise la programmation dynamique, une technique qui décompose le problème en sous-problèmes plus petits et réutilise les résultats intermédiaires pour éviter les calculs redondants.

Comment Ça Marche ?

1. Initialisation : Pour chaque élément du tableau, on initialise une valeur msis (Maximum Sum Increasing Subsequence) égale à l'élément lui-même.
2. Itération : On parcourt le tableau. Pour chaque élément arr[i], on compare avec les éléments précédents arr[j] (où j < i).
3. Condition d'Optimisation : Si arr[i] est supérieur à arr[j] (pour assurer l'ordre croissant) et si la somme msis[j] + arr[i] est supérieure à msis[i], alors on met à jour msis[i] avec cette nouvelle somme.
4. Résultat : Après avoir parcouru tout le tableau, on recherche la valeur maximale dans msis. Cette valeur représente la somme maximale de la sous-séquence croissante.

Avantages de cette approche :

• Efficacité : La programmation dynamique évite de recalculer les résultats intermédiaires, optimisant ainsi le temps d'exécution.
• Simplicité : L'algorithme est relativement facile à comprendre et à implémenter.

Exemples de Code : Visualisez la Solution

Voici des exemples de code dans différents langages pour illustrer l'implémentation de l'algorithme :

C++

/* Dynamic Programming implementation
 of Maximum Sum Increasing Subsequence
 (MSIS) problem */
#include <iostream>
using namespace std;

/* maxSumIS() returns the maximum
 sum of increasing subsequence
 in arr[] of size n */
int maxSumIS(int arr[], int n)
{
    int i, j, max = 0;
    int msis[n];

    /* Initialize msis values
    for all indexes */
    for( i = 0; i < n; i++ )
        msis[i] = arr[i];

    /* Compute maximum sum values
    in bottom up manner */
    for( i = 1; i < n; i++ )
        for( j = 0; j < i; j++ )
            if(arr[i] > arr[j] &&
                msis[i] < msis[j] + arr[i])
                msis[i] = msis[j] + arr[i];

    /* Pick maximum of
    all msis values */
    for( i = 0; i < n; i++ )
        if( max < msis[i] )
            max = msis[i];

    return max;
}

// Driver Code
int main()
{
    int arr[] = {1, 101, 2, 3, 100, 4, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Sum of maximum sum increasing "
            "subsequence is " << maxSumIS( arr, n ) << endl;
    return 0;
}

// This is code is contributed by rathbhupendra

Java

/* Dynamic Programming Java
    implementation of Maximum Sum
    Increasing Subsequence (MSIS)
    problem */
class GFG
{
    /* maxSumIS() returns the
        maximum sum of increasing
        subsequence in arr[] of size n */
    static int maxSumIS(int arr[], int n)
    {
        int i, j, max = 0;
        int msis[] = new int[n];

        /* Initialize msis values
            for all indexes */
        for (i = 0; i < n; i++)
            msis[i] = arr[i];

        /* Compute maximum sum values
            in bottom up manner */
        for (i = 1; i < n; i++)
            for (j = 0; j < i; j++)
                if (arr[i] > arr[j] &&
                        msis[i] < msis[j] + arr[i])
                    msis[i] = msis[j] + arr[i];

        /* Pick maximum of all
            msis values */
        for (i = 0; i < n; i++)
            if (max < msis[i])
                max = msis[i];

        return max;
    }

    // Driver code
    public static void main(String args[])
    {
        int arr[] = new int[]{1, 101, 2, 3, 100, 4, 5};
        int n = arr.length;
        System.out.println("Sum of maximum sum "
                           +"increasing subsequence is "
                           + maxSumIS(arr, n));
    }
}
// This code is contributed
// by Rajat Mishra

Python3

# Dynamic Programming based Python
# implementation of Maximum Sum
# Increasing Subsequence (MSIS)
# problem

# maxSumIS() returns the maximum
# sum of increasing subsequence
# in arr[] of size n
def maxSumIS(arr, n):
    max_sum = 0
    msis = [0 for x in range(n)]

    # Initialize msis values
    # for all indexes
    for i in range(n):
        msis[i] = arr[i]

    # Compute maximum sum
    # values in bottom up manner
    for i in range(1, n):
        for j in range(i):
            if (arr[i] > arr[j] and
                    msis[i] < msis[j] + arr[i]):
                msis[i] = msis[j] + arr[i]

    # Pick maximum of
    # all msis values
    for i in range(n):
        if max_sum < msis[i]:
            max_sum = msis[i]

    return max_sum

# Driver Code
arr = [1, 101, 2, 3, 100, 4, 5]
n = len(arr)
print("Sum of maximum sum increasing " +
            "subsequence is " +
            str(maxSumIS(arr, n)))

# This code is contributed
# by Bhavya Jain

Complexité

• Temps : O(n^2), où n est la longueur du tableau.
• Espace : O(n), pour stocker les sommes intermédiaires dans le tableau msis.

Conclusion : Maîtrisez l'Art des Sous-Séquences

Vous avez maintenant les outils pour identifier et calculer la sous-séquence croissante de somme maximale. Expérimentez avec les exemples de code et adaptez-les à vos propres défis algorithmiques.

Alors, prêt à impressionner avec vos nouvelles compétences en programmation dynamique ?