Description du problème: un tableau avec n éléments, ces n éléments peuvent être positifs ou négatifs. Trouvez la somme du plus grand sous-réseau.
Méthode 1: Méthode de force brute
Idée: la façon la plus simple et la plus simple de penser est de trouver tous les sous-réseaux, de trouver la somme de toutes les sous-réseaux et d'obtenir la valeur maximale dans la somme de tous les sous-réseaux.
/ ** * Méthode 1 (méthode de force brute): Trouvez la somme des sous-réseaux maximaux en deux boucles * / public static int maxSubArray1 (int [] a) {int i, j; int thissum = 0; int maxsum = 0; pour (i = 0; i <a.Length; i ++) {thisSum = a [i]; pour (j = i + 1; j <a.length; j ++) {thissum + = a [j]; if (thissum> maxsum) {maxsum = thissum; }} return maxsum; }Méthode 2: Programmation dynamique optimisée
Idée: Premièrement, selon la relation entre le dernier élément A [n-1] du tableau et le plus grand sous-réseau, il peut être divisé en trois situations suivantes:
1) Le sous-réseau maximal contient un [N-1], c'est-à-dire se terminant par un [N-1].
2) A [N-1] seul forme le plus grand sous-réseau.
3) Le sous-réseau maximal ne contient pas de [N-1], donc trouver le sous-réseau maximal d'un [1, ..., n-1] peut être converti pour trouver le sous-réseau maximal d'un [1, ..., N-2].
Grâce à l'analyse ci-dessus, nous pouvons tirer la conclusion suivante: en supposant que la somme du plus grand tableau de (A [0], ... A [I-1]) a été calculée comme tous [I-1], et la somme du plus grand tableau de A [i-1] dans (a [0], ... a [i-1]) est également calculée comme fin [i-1].
Ensuite, la relation suivante peut être obtenue: tous [i-1] = max {a [i-1], end [i-1], tous [i-1]}. Utilisez cette formule et l'idée de programmation dynamique pour résoudre les problèmes. (Le code résout également le problème de la position de départ et de la position de fin)
/ ** * Méthode 2: La méthode de programmation dynamique optimisée * Nend est obtenue en ajoutant des tableaux à un [i] en séquence, puis en les comparant à un [i] ", et en enregistrant le plus grand. Parce que si le numéro précédent est ajouté à un [i] * n'est pas aussi grand qu'un [i] lui-même, alors le nombre précédent n'aura pas la plus grande contribution. Avant * / public static int max (int m, int n) {return m> n? m: n;} public static int maxsubarray2 (int [] a) {int nall = a [0]; // la somme des sous-terrains maximaux de n Arrays numériques int nend = a [0]; // la somme des sous-terrassements de n Numériques contient le dernier élément pour (int i = 1; i ++) {nend = max (nend + a [i], a [i]); nall = max (nend, nall); maxsum = Integer.min_value; int nsum = 0; int nstart = 0; for (int i = 0; i <a.length; i ++) {if (nsum <0) {nsum = a [i]; nStart = i; } else {nsum + = a [i]; } if (nsum> maxsum) {maxsum = nsum; begin = nstart; end = i; }} return maxsum; }Ce qui précède est tout le contenu de cet article. J'espère que le contenu de cet article sera d'une aide à l'étude ou au travail de chacun. J'espère également soutenir plus Wulin.com!