Angenommen, es gibt Sequenzen: 2, 1, 3, 5, stellen Sie fest, dass die längste Ascender -Sequenz 2, 3, 5 oder 1, 3, 5 beträgt und die Länge 3 beträgt.
Die Idee des LIS -Algorithmus ist:
Angenommen, es gibt eine Sequenz a.
① Wenn es nur ein Element gibt, dann ist die Länge der längsten Ascender -Sequenz 1;
② Wenn es zwei Elemente gibt, wenn a [1]> A [0], ist die Länge der längsten Ascender -Sequenz 2, A [1] das letzte Element der längsten Ascender -Sequenz; Wenn a [1] <a [0], beträgt die Länge der längsten Ascender -Sequenz 1 und A [0] und A [1] beide die letzten Elemente seiner längsten Ascender -Sequenz.
③ Wenn es aus drei Elementen besteht, kann ein [2] [2] ein [2] das letzte Element der längsten aufsteigenden Subsequenz sein, in der sich A [0] oder A [1] befindet. Dann hängt die zu wählene Sequenz davon ab, welche Sequenz A [0] und A [1] länger ist.
④ Um auf N -Elemente zu expandieren, wird die Länge der längsten Ascender -Sequenz mit einem [n] als letztem Element angezeigt.
Definieren Sie zwei Arrays, einer ist a und der andere ist b.
A speichert die Originaldaten und b [i] die Länge der längsten Ascender -Sequenz, die mit einem [i] endet.
Der Code ist wie folgt:
Klasse LMAX {public static void lmax (int [] a, int [] b) {b [0] = 1; für (int i = 1; i <A.Length; i ++) {int countMax = 0; für (int j = 0; j <i; j ++) {if (a [i]> a [j] && b [j]> countmax) {countMax = b [j]; // Aufzeichnen Sie die Subsequenzlänge, deren Elementwert kleiner als a [i] ist, entspricht jedoch der längsten Subquenz}} b [i] = countMax+1; // Die längste Subsequenzlänge, die einem [i] entsprechend}}} entspricht, ist}}}2. Geh aus der Formation aus
Titelbeschreibung:
In der High School organisierte die Schule alle Lehrer und Schüler jeden Morgen, um zu trainieren. Immer wenn die Übungsordnung ertönte, rannten alle nach unten, und dann waren die kurzgeheimen vor der Linie gesäumt, während die größeren am Ende der Linie ausgekleidet waren. Plötzlich, eines Tages, hatte die für das Team verantwortliche Person eine Idee und wollte die Formation ändern. Das heißt, als alle aus dem Obergeschoss rannten, waren alle Schüler zufällig in Folge besetzt, und die Person, die für das Team verantwortlich war, nahm einen Teil der Schüler aus dem Team heraus, so dass die Höhe der verbleibenden Schüler im Team eine "Spitzenform" war, die zuerst stieg und dann von vorne fiel. Es wird gesagt, dass eine solche Form allen Glück bringen kann, und ich wünsche Ihnen allen, dass Sie auf der Straße des Lernens die Spitze klettern können. (Beachten Sie, dass nur eine Seite des Berges die Bedingungen erfüllt, z. B. 1, 1, 2, 2 und 1 den Bedingungen)
eingeben:
Der Eingang kann mehrere Testproben enthalten.
Für jeden Testfall handelt es sich bei der ersten Zeile um eine Ganzzahl n (1 <= n <= 1000000): Repräsentiert die Anzahl der zu ermittelten Schüler.
Die zweite Eingabezeile umfasst N -Ganzzahlen: Repräsentiert die Höhe des Schülers (CM) (eine positive Ganzzahl mit einer Höhe von nicht mehr als 200).
Ausgabe:
Für jeden Testfall wird die minimale Anzahl von Schülern ausgezogen.
Probeneingang:
6
100 154 167 159 132 105
5
152 152 152 152 152 152
Beispielausgabe:
0
4
Wenn Sie LIS zur Lösung dieses Problems verwenden, können Sie dies in Betracht ziehen:
Verwenden Sie zuerst LIS, um die Länge der längsten Ascender -Sequenz zu finden, die mit jedem Element von vorne nach hinten endet, und verwenden Sie LIS, um die Länge der längsten Ascender -Sequenz zu finden, die mit jedem Element endet.
Holen Sie sich zwei Arrays B1, B2.
B1 und B2 entsprechen der entsprechenden Addition und Subtrahiere des wiederholten, der längste "Berg".
public class Peak {public static void main (String [] args) {int n; int re; do {scanner in = new scanner (System.in); n = in.Nextint (); } while (n <0 || n> 100000); int [] a = new int [n]; // Original Array int [] ar = new int [n]; // Inverse Array Scanner in = neuer Scanner (System.in); für (int i = 0; i <n; i ++) {a [i] = in.nextint (); } int [] b1 = new int [n]; @SuppressWarnings ("unbenutzt") int [] b2 = new int [n]; Lmax.lmax (a, b1); ar = reverse.reverse (a); Lmax.lmax (ar, b2); // die längste aufsteigende Untersequenz des inversen Arrays b2 = reverse.reverse (B2) lösen; // Inverse die längste aufsteigende Untersequenz des inversen Arrays, um die entsprechende Entsprechung der längsten aufsteigenden Subsequenz des ursprünglichen Array -RE = -Ergebniss hinzuzufügen.Result (B1, B2); System.out.print (re); }} <br> <br> <br> <br> Klassenergebnis {public static int Ergebnis (int [] a, int [] b) {int max = 0; int [] c = new int [A.Length]; für (int i = 0; i <A.Length; i ++) {c [i] = a [i]+b [i]; } Arrays.sort (c); max = c [C.Length-1] -1; // die entsprechende Person mit der längsten Addition und Subtrahiere der wiederholten Rückgabe A. Length-Max; }}Das obige ist der gesamte Inhalt des Problems der Verwendung von Java zur Implementierung des LIS -Algorithmus und zur Herstellung von Formationen. Ich hoffe, es wird für alle hilfreich sein und wulin.com mehr ~ unterstützen ~