Découvrez Comment Trouver la Sous-Séquence Croissante de Somme Maximale : Guide Simple et Efficace

Vous cherchez à optimiser vos compétences en algorithmique ? Comprendre la sous-séquence croissante de somme maximale (Maximum Sum Increasing Subsequence ou MSIS) est essentiel. Cet article vous guide à travers les concepts et les solutions de manière claire et accessible.

Pourquoi Maîtriser la Sous-Séquence Croissante de Somme Maximale ?

Connaître cet algorithme vous offre plusieurs avantages :

Résoudre des problèmes complexes : Apprenez à décomposer des défis en étapes plus petites.
Optimisation : Améliorez l'efficacité de vos codes et algorithmes.
Préparation aux entretiens techniques : Impressionnez les recruteurs avec vos compétences.

Qu'est-ce que la Sous-Séquence Croissante de Somme Maximale ?

Il s'agit d'un problème algorithmique qui consiste à trouver une sous-séquence dans un tableau donné, où les éléments sont triés par ordre croissant, et la somme de ces éléments est la plus grande possible.

Sous-séquence : Une séquence que l'on peut obtenir en supprimant zéro ou plusieurs éléments d'un tableau, sans changer l'ordre des éléments restants.
Croissante : Chaque élément de la sous-séquence est supérieur ou égal à l'élément précédent.
Somme Maximale : La somme de tous les éléments dans la sous-séquence doit être la plus grande possible.

Comment Trouver la Solution ? Explication pas à pas

Utilisons la programmation dynamique pour résoudre ce problème efficacement. Voici les étapes clés :

Initialisation : Créez un tableau msis de la même taille que le tableau d'entrée. Initialisez chaque élément de msis avec la valeur correspondante du tableau d'entrée.
Itération : Parcourez le tableau d'entrée de gauche à droite. Pour chaque élément arr[i], parcourez tous les éléments précédents arr[j] (où j < i).
Comparaison et mise à jour : Si arr[i] est supérieur à arr[j] et que msis[i] est inférieur à msis[j] + arr[i], alors mettez à jour msis[i] avec la valeur msis[j] + arr[i].
Trouver le maximum : Une fois l'itération terminée, parcourez le tableau msis et trouvez la valeur maximale. Cette valeur est la somme de la sous-séquence croissante maximale.

Exemples Concrets Pour Une Meilleure Compréhension

Prenons un exemple simple : arr = {1, 101, 2, 3, 100, 4, 5}.

GeeksforGeeks

La sous-séquence croissante de somme maximale est {1, 2, 3, 100}, et sa somme est 106. Les algorithmes présentés ci-dessous implémentent cette logique.

Code Source : C++, C, Java, Python3, C#, PHP, Javascript

Retrouvez ci-dessous des exemples de code dans divers langages de programmation. Les codes ci-dessous appliquent l'algorithme décrit précédemment, en utilisant la programmation dynamique pour une efficacité optimale.

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;
}

C

/* Dynamic Programming implementation
 of Maximum Sum Increasing Subsequence
 (MSIS) problem */
#include <stdio.h>

/* 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]);
    printf("Sum of maximum sum increasing "
            "subsequence is %d\n",
             maxSumIS( arr, n ) );
    return 0;
}

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));
    }
}

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 = 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 < msis[i]:
            max = msis[i]

    return max

# 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)))

C#

// Dynamic Programming C# implementation
// of Maximum Sum Increasing Subsequence
// (MSIS) problem
using System;
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()
    {
        int []arr = new int []{1, 101, 2, 3, 100, 4, 5};
        int n = arr.Length;
        Console.WriteLine("Sum of maximum sum increasing " +
                                            " subsequence is " +
                                            maxSumIS(arr, n));
    }
}

PHP

<?php
// Dynamic Programming implementation
// of Maximum Sum Increasing
// Subsequence (MSIS) problem 

// maxSumIS() returns the maximum 
// sum of increasing subsequence 
// in arr[] of size n 
function maxSumIS( $arr , $n ) 
{ 
    $max = 0; 
    $msis = array ( $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 
    $arr = array (1, 101, 2, 3, 100, 4, 5); 
    $n = count ( $arr ); 
    echo "Sum of maximum sum increasing subsequence is "
                                        .maxSumIS( $arr , $n ); 
        
// This code is contributed by Sam007 
?>

Javascript

 // Dynamic Programming implementation 
// of Maximum Sum Increasing Subsequence 
// (MSIS) problem 
 
// maxSumIS() returns the maximum 
// sum of increasing subsequence 
// in arr[] of size n 
function maxSumIS(arr, n) 
{ 
    let i, j, max = 0; 
    let msis = new Array(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 
let arr = [ 1, 101, 2, 3, 100, 4, 5 ]; 
let n = arr.length; 
document.write("Sum of maximum sum increasing "+ 
                    "subsequence is "+ maxSumIS(arr, n));

Complexité Temporelle et Spatiale

Complexité Temporelle : O(n^2), car nous avons deux boucles imbriquées.
Complexité Spatiale : O(n), pour stocker le tableau msis.

Prêt à relever le défi ?

Maîtriser la sous-séquence croissante de somme maximale est une étape importante pour devenir un développeur plus compétent. En comprenant les concepts et les solutions, vous serez mieux préparé pour résoudre des problèmes complexes et exceller dans votre carrière.

Pourquoi Maîtriser la Sous-Séquence Croissante de Somme Maximale ?

Connaître cet algorithme vous offre plusieurs avantages :

Résoudre des problèmes complexes : Apprenez à décomposer des défis en étapes plus petites.

Optimisation : Améliorez l'efficacité de vos codes et algorithmes.

Préparation aux entretiens techniques : Impressionnez les recruteurs avec vos compétences.

Qu'est-ce que la Sous-Séquence Croissante de Somme Maximale ?

Sous-séquence : Une séquence que l'on peut obtenir en supprimant zéro ou plusieurs éléments d'un tableau, sans changer l'ordre des éléments restants.

Croissante : Chaque élément de la sous-séquence est supérieur ou égal à l'élément précédent.

Somme Maximale : La somme de tous les éléments dans la sous-séquence doit être la plus grande possible.

Comment Trouver la Solution ? Explication pas à pas

Utilisons la programmation dynamique pour résoudre ce problème efficacement. Voici les étapes clés :

Initialisation : Créez un tableau msis de la même taille que le tableau d'entrée. Initialisez chaque élément de msis avec la valeur correspondante du tableau d'entrée.

Itération : Parcourez le tableau d'entrée de gauche à droite. Pour chaque élément arr[i], parcourez tous les éléments précédents arr[j] (où j < i).

Comparaison et mise à jour : Si arr[i] est supérieur à arr[j] et que msis[i] est inférieur à msis[j] + arr[i], alors mettez à jour msis[i] avec la valeur msis[j] + arr[i].

Trouver le maximum : Une fois l'itération terminée, parcourez le tableau msis et trouvez la valeur maximale. Cette valeur est la somme de la sous-séquence croissante maximale.

Code Source : C++, C, Java, Python3, C#, PHP, Javascript

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; }

Java

Python3

PHP

Javascript