Supposons qu'il y ait des séquences: 2, 1, 3, 5, découvrez que la séquence ascension la plus longue est de 2, 3, 5 ou 1, 3, 5 et que la longueur est 3.
L'idée de l'algorithme LIS est:
Supposons qu'il y ait une séquence a.
① S'il n'y a qu'un seul élément, alors la longueur de la séquence ascendante la plus longue est 1;
② S'il y a deux éléments, si A [1]> A [0], la longueur de la séquence ascension la plus longue est 2, A [1] est le dernier élément de la séquence ascension la plus longue; Si A [1] <A [0], la longueur de la séquence ascension la plus longue est 1, et A [0] et A [1] sont tous deux les derniers éléments de sa séquence ascendante la plus longue.
③ S'il est composé de trois éléments, si A [2]> A [0], A [2]> A [1], alors un [2] peut être le dernier élément de la sous-séquence ascendant la plus longue où se trouve une [0] ou un [1]. Ensuite, la séquence à choisir dépend de la séquence A [0] et A [1] plus longue.
④ Pour s'étendre à N éléments, c'est pour voir la longueur de la séquence ascension la plus longue avec un [n] comme dernier élément.
Définissez deux tableaux, l'un est A et l'autre est b.
A stocke les données d'origine et b [i] stocke la longueur de la séquence ascension la plus longue se terminant par un [i].
Le code est le suivant:
classe lmax {public static void lmax (int [] a, int [] b) {b [0] = 1; for (int i = 1; i <a.length; i ++) {int countMax = 0; pour (int j = 0; j <i; j ++) {if (a [i]> a [j] && b [j]> countMax) {countmax = b [j]; // Enregistrez la longueur de la subséquence dont la valeur de l'élément est inférieure à un [i] mais correspond à la sous-séquence la plus longue}} b [i] = countMax + 1; // La longueur de subséquence la plus longue correspondant à un [i] est}}}2. Sortez de la formation
Description du titre:
Au lycée, l'école a organisé tous les enseignants et les élèves à courir chaque matin pour faire de l'exercice. Chaque fois que l'ordre d'exercice sonnait, tout le monde a commencé à courir en bas, puis ceux qui étaient à talent courte étaient bordés devant la ligne, tandis que les plus grands étaient bordés à la fin de la ligne. Soudain, un jour, la personne en charge de l'équipe a eu une idée et a voulu changer la formation. Autrement dit, lorsque tout le monde a couru de l'étage supérieur, tous les étudiants ont été occupés au hasard dans une rangée, et la personne en charge de l'équipe a sorti une partie des étudiants de l'équipe, de sorte que la hauteur des étudiants restants de l'équipe était une forme "de pic" qui s'est d'abord augmentée et est tombée de l'avant. On dit qu'une telle forme peut porter chance à tous, et je vous souhaite à tous grimper le sommet sur la route de l'apprentissage. (Remarque, un seul côté de la montagne remplit les conditions, comme 1, 1, 2, 2 et 1 remplit les conditions)
entrer:
L'entrée peut contenir plusieurs échantillons de test.
Pour chaque cas de test, la première ligne entrée est un entier n (1 <= n <= 1000000): représente le nombre d'étudiants à saisir.
La deuxième ligne d'entrée comprend n entières: représente la hauteur de l'élève (CM) (un entier positif avec une hauteur pas supérieur à 200).
Sortir:
Pour chaque cas de test, le nombre minimum d'étudiants à dessiner est la sortie.
Exemple d'entrée:
6
100 154 167 159 132 105
5
152 152 152 152 152 152
Exemple de sortie:
0
4
Lorsque vous utilisez LIS pour résoudre ce problème, vous pouvez considérer ceci:
Tout d'abord, utilisez LIS pour trouver la longueur de la séquence ascendante la plus longue se terminant avec chaque élément d'avant en arrière, puis utilisez LIS pour trouver la longueur de la séquence ascension la plus longue se terminant avec chaque élément.
Obtenez deux tableaux B1, B2.
B1 et B2 correspondant à l'ajout correspondant et soustrayant celui répété est la «montagne» la plus longue.
classe publique Peak {public static void main (String [] args) {int n; int re; do {scanner dans = new Scanner (System.in); n = in.Nextint (); } while (n <0 || n> 100000); int [] a = new int [n]; // Array original int [] ar = new int [n]; // Scanner de tableau inverse dans = nouveau scanner (System.in); pour (int i = 0; i <n; i ++) {a [i] = in.nextint (); } int [] b1 = new int [n]; @SuppressWarnings ("inutilisé") int [] b2 = new int [n]; Lmax.lmax (a, b1); ar = reverse.reverse (a); Lmax.lmax (ar, b2); // Résoudre la sous-séquence ascendante la plus longue du réseau inverse B2 = Reverse.Reverse (B2); // inverse la plus longue sous-séquence ascendante du réseau inverse afin d'ajouter le correspondant correspondant à la sous-séquence ascendante la plus longue du tableau d'origine re = result.result (b1, b2); System.out.print (RE); }} <br> <br> <br> <br> Résultat de classe {public static int result (int [] a, int [] b) {int max = 0; int [] c = new int [a.length]; for (int i = 0; i <a.length; i ++) {c [i] = a [i] + b [i]; } Arrays.sort (c); max = c [c.length-1] -1; // la personne correspondante avec l'ajout le plus long et la soustraction du retour répété a.Length-max; }}Ce qui précède est tout le contenu du problème de l'utilisation de Java pour implémenter l'algorithme LIS et la création de formations. J'espère que ce sera utile à tout le monde et soutenir Wulin.com plus ~