Somme maximale des éléments non consécutifs (programmation dynamique)

csguy

Étant donné un tableau d'entiers positifs, quel est l'algorithme le plus efficace pour trouver des éléments non consécutifs de ce tableau qui, lorsqu'ils sont additionnés, produisent la somme maximale?

La solution de programmation dynamique consiste à utiliser un tableau auxiliaire maxSumcontenant la somme maximale jusqu'à cet index particulier. Nous commençons par définir les 2 premiers indices du tableau et remplissons le reste du tableau avec max(array[i]+maxSum[i-2], maxSum[i-1]).

Je comprends que nous ne pouvons pas ajouter d'éléments adjacents, mais j'ai du mal à comprendre comment la solution ci-dessus prend en considération le fait qu'il est possible que l'élément précédent maxSum[i]ne soit pas le résultat d'une sommation avec array[i].

Par exemple:

index:  0 1 2  3 4

array:  3 5 -7 8 10

maxSum: 3 5 5  _

Nous voyons que maxSum [2] n'est pas le résultat d'une sommation avec le tableau [2].

A trouver maxSum[3] = max(array[3]+maxSum[1], maxSum[2]), mais pourquoi ne pas envisager maxSum[2] + array[3]? Puisqu'il est possible que maxSum [2] ne soit pas constitué de la valeur du tableau adjacent [2].

Gilad Barkan

Comment la solution ci-dessus prend-elle en considération le fait qu'il est possible que l'élément précédent dans maxSum [i] ne soit pas le résultat de la somme avec le tableau [i]?

Simplement. Si l'élément précédent dans maxSum [i] ne doit pas être inclus dans le résultat de la somme avec le tableau [i], nous pouvons regarder maxSum [i - 2]. Nous faisons cela explicitement dans

array[i]+maxSum[i-2]

nous comparons cela à l'option de ne pas inclure le tableau [i], qui est

maxSum[i-1]

Articles connexes

Coller ensemble des éléments non numériques consécutifs

Cristian E. Nuno Question Après avoir identifié des éléments dans un vecteur de caractères qui satisfont un modèle non numérique, comment puis-je coller ensemble ces éléments qui satisfont consécutivement le modèle d' expression régulière ? Aperçu sample_text

somme maximale de n éléments consécutifs du tableau

swap96 Comment trouver la somme maximale des nnombres consécutifs d'un tableau? Par exemple, si notre tableau est {2,5,3,4,6}et que la n == 2sortie doit être 10(ie 6 + 4). Je suis en mesure d'obtenir la bonne logique pour les petites valeurs de taille de table

Somme des éléments consécutifs du tableau

ozil J'ai un tableau comme ci-dessous var data = [{ category: "2014-1-1", subCategory: [{ name: "shoe", val: 70, toolTip: "toolTip-shoe-70", drill: false }, { name: "pant", val: 60, toolTip: "

Somme des incréments consécutifs

Braedin Jared J'essaie de déterminer l'incrément que je voudrais utiliser pour atteindre un nombre spécifique dans un nombre spécifique d'itérations. Par exemple, mon numéro d'objectif est 100 et mon numéro de départ est 1. Quel incrément ajouté à 1 à chaque f

somme maximale de n jours consécutifs utilisant des pandas

Naru J'ai vu des solutions dans différents langages (c'est-à-dire SQL, fortran ou C++) qui font principalement des boucles for. J'espère que quelqu'un pourra m'aider à résoudre cette tâche en utilisant plutôt des pandas. Si j'ai un bloc de données qui ressembl