Supongamos que hay secuencias: 2, 1, 3, 5, encuentran que la secuencia de ascender más larga es 2, 3, 5 o 1, 3, 5, y la longitud es 3.
La idea del algoritmo LIS es:
Supongamos que hay una secuencia a.
① Si solo hay un elemento, entonces la longitud de la secuencia de ascender más larga es 1;
② Si hay dos elementos, si a [1]> a [0], la longitud de la secuencia de ascender más larga es 2, A [1] es el último elemento de la secuencia de ascender más larga; Si A [1] <a [0], la longitud de la secuencia de ascender más larga es 1, y A [0] y A [1] son los últimos elementos de su secuencia de ascender más larga.
③ Si está hecho de tres elementos, si a [2]> A [0], A [2]> A [1], entonces A [2] puede ser el último elemento de la subsecución ascendente más larga donde se encuentra un [0] o A [1]. Entonces qué secuencia elegir depende de qué secuencia A [0] y A [1] es más larga.
④ Para expandirse a n elementos, es ver la longitud de la secuencia de ascender más larga con un [n] como el último elemento.
Definir dos matrices, una es A y la otra es b.
A almacena los datos originales, y B [i] almacena la longitud de la secuencia de ascender más larga que termina con un [i].
El código es el siguiente:
clase lmax {public static void lmax (int [] a, int [] b) {b [0] = 1; para (int i = 1; i <a.length; i ++) {int countmax = 0; for (int j = 0; j <i; j ++) {if (a [i]> a [j] && b [j]> countmax) {countmax = b [j]; // Registre la longitud de subsecuencia cuyo valor de elemento es menor que un [i] pero corresponde a la posterior posterior más larga}} b [i] = Countmax+1; // La longitud posterior más larga correspondiente a un [i] es}}}2. Salga de la formación
Descripción del título:
Cuando estaba en la escuela secundaria, la escuela organizó a todos los maestros y estudiantes a correr todas las mañanas para hacer ejercicio. Cada vez que sonaba la orden de ejercicio, todos comenzaron a correr por las escaleras, y luego los cortos se alineaban frente a la línea, mientras que los más altos estaban alineados al final de la línea. De repente, un día, a la persona a cargo del equipo se le ocurrió una idea y quería cambiar la formación. Es decir, cuando todos corrieron desde el piso superior, todos los estudiantes estaban ocupados al azar en una fila, y la persona a cargo del equipo sacó una parte de los estudiantes del equipo, de modo que la altura de los estudiantes restantes en el equipo era una forma "máxima" que se levantó primero y luego cayó desde el frente. Se dice que tal forma puede traer buena suerte a todos, y les deseo que suban la cima en el camino del aprendizaje. (Tenga en cuenta que solo un lado de la montaña cumple con las condiciones, como 1, 1, 2, 2 y 1 cumple con las condiciones)
ingresar:
La entrada puede contener múltiples muestras de prueba.
Para cada caso de prueba, la primera línea ingresada es un entero N (1 <= n <= 1000000): representa el número de estudiantes que se ingresarán.
La segunda línea de entrada incluye n enteros: representa la altura del alumno (cm) (un entero positivo con una altura no superior a 200).
Producción:
Para cada caso de prueba, el número mínimo de estudiantes a dibujar es la salida.
Entrada de muestra:
6
100 154 167 159 132 105
5
152 152 152 152 152 152
Salida de muestra:
0
4
Al usar LIS para resolver este problema, puede considerar esto:
Primero, use LIS para encontrar la longitud de la secuencia de ascender más larga que termina con cada elemento de adelante hacia atrás, luego use LIS para encontrar la longitud de la secuencia de ascender más larga que termina con cada elemento.
Obtenga dos matrices B1, B2.
B1 y B2 correspondiente a la adición correspondiente y restando la repetida es la 'montaña' más larga.
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]; // matriz original int [] ar = new int [n]; // escáner de matriz inversa en = nuevo escáner (System.in); para (int i = 0; i <n; i ++) {a [i] = in.nextInt (); } int [] b1 = new int [n]; @Suppleswarnings ("sin usar") int [] b2 = new int [n]; Lmax.lmax (a, b1); ar = reverse.reverse (a); Lmax.lmax (AR, B2); // Resuelve la posterior subsecuencia ascendente más larga de la matriz inversa B2 = reverso.reverse (B2); // Inverso La subsecuencia ascendente más larga de la matriz inversa para agregar la correspondiente correspondiente a la subsecuencia ascendente más larga de la matriz original re = resultado.result (b1, b2); System.out.print (RE); }} <br> <br> <br> <br> Resultado de clase {public static int result (int [] a, int [] b) {int max = 0; int [] c = new int [a.length]; para (int i = 0; i <a.length; i ++) {c [i] = a [i]+b [i]; } Arrays.sort (c); max = c [C.Length-1] -1; // la persona correspondiente con la adición más larga y restando el retorno repetido a.length-max; }}Lo anterior es todo el contenido del problema de usar Java para implementar el algoritmo LIS y hacer formaciones. Espero que sea útil para todos y apoye a Wulin.com más ~