Comment utiliser le sous-tableau maximum et l'algorithme en C++

Comment utiliser l'algorithme de somme maximale de sous-tableaux en C++

Le problème de la somme maximale de sous-tableaux est un problème d'algorithme classique, qui nécessite de trouver un sous-tableau continu dans un tableau d'entiers donné tel que tous les sous-tableaux La somme des éléments est la le plus grand. Ce problème peut être résolu en utilisant l'idée de programmation dynamique.

Une solution simple mais inefficace consiste à trouver tous les sous-tableaux possibles par une méthode exhaustive, à calculer leur somme, puis à trouver la plus grande somme. La complexité temporelle de cette méthode est O(n^3), ce qui sera très lent lorsque la longueur du tableau est grande.

Une solution plus efficace repose sur l'idée de programmation dynamique. Nous pouvons enregistrer la somme maximale des sous-tableaux se terminant par chaque élément en définissant un tableau auxiliaire dp. dp[i] représente la plus grande somme de sous-tableau se terminant par le i-ème élément. Pour dp[i], il y a deux situations :

1. Si dp[i-1] est supérieur à 0, alors dp[i] = dp[i-1] + arr[i]; -1 ] est inférieur ou égal à 0, alors dp[i] = arr[i].
2. Nous calculons chaque élément du tableau dp en parcourant l'ensemble du tableau, et mettons simultanément à jour le plus grand sous-tableau et max_sum ainsi que les indices de début et de fin correspondants start et end. Lorsqu'une somme de sous-tableau plus grande est trouvée, nous mettons à jour la valeur correspondante. Enfin, la somme maximale du sous-tableau est max_sum, et l'indice de début du sous-tableau est start et l'indice de fin est end.

Ce qui suit est un exemple de code pour implémenter le sous-tableau maximum et l'algorithme en langage C++ :

#include <iostream>
#include <vector>

using namespace std;

vector<int> maxSubarraySum(vector<int>& arr) {
    int n = arr.size();
    int dp[n];
    dp[0] = arr[0];
    int max_sum = dp[0];
    int start = 0, end = 0;

    for(int i = 1; i < n; i++) {
        if(dp[i-1] > 0)
            dp[i] = dp[i-1] + arr[i];
        else {
            dp[i] = arr[i];
            start = i;
        }
        
        if(dp[i] > max_sum) {
            max_sum = dp[i];
            end = i;
        }
    }
    
    vector<int> result;
    result.push_back(max_sum);
    result.push_back(start);
    result.push_back(end);

    return result;
}

int main() {
    vector<int> arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    vector<int> result = maxSubarraySum(arr);
    
    cout << "最大子数组和：" << result[0] << endl;
    cout << "子数组的起始下标：" << result[1] << endl;
    cout << "子数组的终止下标：" << result[2] << endl;

    return 0;
}

Exécutez le code ci-dessus, le résultat de sortie est le suivant :

Somme maximale du sous-tableau : 6

Indice de départ du sous-tableau : 3

de l'indice de terminaison du sous-tableau : 6

Le code ci-dessus résout le problème de la somme maximale du sous-tableau avec une complexité temporelle O(n) grâce à l'idée de programmation dynamique. Cet algorithme est très efficace lorsqu’il s’agit de grands tableaux.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!