Problembeschreibung: Ein Array mit N -Elementen kann diese N -Elemente positiv oder negativ sein. Finden Sie die Summe der größten Subtarray.
Methode 1: Brute -Force -Methode
Idee: Der einfachste und einfachste Weg, an den man denken kann, besteht darin, alle Subtarrays zu finden, dann die Summe aller Subtarrays zu finden und den Maximalwert in der Summe aller Subaarrays zu erhalten.
/ *** Methode 1 (Brute -Force -Methode): Finden Sie die Summe der maximalen Subarrays in zwei Schleifen*/ public static int maxsubarray1 (int [] a) {int i, j; int thisumsum = 0; int maxsum = 0; für (i = 0; i <A.Length; i ++) {thisSum = a [i]; für (j = i+1; j <A.Length; j ++) {thisSum+= a [j]; if (thisSum> maxsum) {maxsum = thisSum; }} return maxsum; }Methode 2: Optimierte dynamische Programmierung
Idee: Erstens kann nach der Beziehung zwischen dem letzten Element A [n-1] des Arrays und dem größten Subtarray in die folgenden drei Situationen unterteilt werden:
1) Das maximale U-Boot enthält ein [N-1], das heißt mit einem [N-1].
2) A [n-1] allein bildet die größte Subtarray.
3) Das maximale Subaarrray enthält keine [n-1]. Das Finden der maximalen Subriten eines [1, ..., n-1] kann also in das Finden der maximalen Subareray von A [1, ..., N-2] umgewandelt werden.
Durch die obige Analyse können wir die folgende Schlussfolgerung ziehen: unter der Annahme, dass die Summe des größten Arrays von (A [0], ... A [I-1]) als alle [i-1] berechnet wurde, und die Summe des größten Arrays eines [I-1] in (a [0], ... a [i-1]) wird auch als Ende berechnet.
Dann kann die folgende Beziehung erhalten werden: alle [i-1] = max {a [i-1], end [i-1], alle [i-1]}. Verwenden Sie diese Formel und die Idee der dynamischen Programmierung, um Probleme zu lösen. (Der Code löst auch das Problem der Startposition und der Endposition)
/*** Methode 2: Optimierte dynamische Programmiermethode* nend wird durch Hinzufügen von Arrays zu einer [i] -Sequenz und dann mit einem [i] vergleicht, und speichert die größere. Denn wenn die vorherige Zahl zu einem [i]* zu einem [i]* nicht so groß ist wie ein [i] selbst. public static int max (int m, int n) {return m> n? m: n; nend = max (nend+a [i], a [i]); maxsum = integer.min_Value; int nstart = 0; für (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; Ende = i; }} return maxsum; }Das obige ist der gesamte Inhalt dieses Artikels. Ich hoffe, dass der Inhalt dieses Artikels für das Studium oder die Arbeit eines jeden hilfreich sein wird. Ich hoffe auch, Wulin.com mehr zu unterstützen!