Este artículo describe la implementación de Java del algoritmo de posterior más largo para las matrices. Compártelo para su referencia, como sigue:
Problema: Dada una variedad de longitud n, encuentre la subsecuencia monotónica de autoincremento más larga (no necesariamente continua, pero el orden no se puede estropear). Por ejemplo: dada una matriz de longitud a {1, 3, 5, 2, 4, 6, 7, 8} con la longitud 8, entonces su secuencia de amplicón monotónico más larga es {1, 2, 4, 6, 7, 8} y su longitud es 6.
Idea 1: Cuando vea la pregunta al principio, muchas personas definitivamente pensarán en LCS primero. Primero ordene la matriz en una nueva matriz y luego use la nueva matriz y la matriz original para encontrar LCS para obtener la respuesta. Muchas personas pueden imaginar esta solución, por lo que no entraré en detalles.
Idea 2: Según la Idea de la Idea 1, aún tiene que usar DP cuando finalmente encuentre LCS. ¿Por qué no usamos DP para resolverlo directamente? Para la matriz ARR, atravesamos la matriz de detrás a delantera y encontramos la posterior posterior más larga cuando la subsecuencia termina con arr[i] , y luego tomamos el valor máximo en el mismo. Puede obtener la posterior posterior más larga de toda la matriz. Entonces, ¿cómo encontrar la posterior posterior más larga que termina con arr[i] ? Esto se convierte en un problema DP. Para requerir la posterior posterior más larga de arr[i] , solo necesita encontrar la posterior posterior más larga de arr[i-1] . Eso es: max{arr[i]}=max{arr[i-1]}+1 .
Código de implementación de Java:
clase pública arrdemo {public static void main (string [] args) {// int [] arr = {89, 256, 78, 1, 46, 78, 8}; int [] arr = {1, 3, 5, 2, 4, 6, 7, 8}; // int [] arr = {6, 4, 8, 2, 17}; int max = 0; int maxlen = arr.length; // atraviesa la matriz desde atrás hacia adelante, y encuentre la longitud de posterior más larga al terminar con arr [i] para (int i = arr.length-1; i> 0; i--) {int [] newarr = new int [i]; System.ArrayCopy (arr, 0, newarr, 0, i); int currentLength = 1 + dp (newarr, arr [i]); if (currentLength> max) max = currentLength; // La longitud más larga de la posterior posterior más larga es la longitud de la matriz original, // Debido a que no necesitamos encontrar el elemento de la posterior posterior más larga, terminamos directamente el bucle para reducir la sobrecarga de tiempo si (max == maxlen) rompe; } System.out.println (max); } public static int dp (int [] arr, int end) {// condición final recursiva if (arr.length == 1) {// Si es menos que final, se incluye en la posterior, la longitud de la posterior +1 if (arr [0] <= end) return 1; else regrese 0; } // atraviesa la matriz y encuentre la posición del elemento más cercana al final y <= end I para (int i = arr.length-1; i> = 0; i--) {if (arr [i] <= end) {// truncar la matriz desde i, y formar una nueva matriz a arr [0] a arr [i-1] para continuar recursivamente encontrando la duración int [] nueva int [nueva int [i]; System.ArrayCopy (arr, 0, newarr, 0, i); // Calcule la posterior posterior más larga cuando contiene ARR [i] y la posterior posterior más larga cuando no contiene ARR [i], respectivamente, y tome el valor máximo int contiene = dp (newarr, arr [i]) + 1; int nocontainlen = dp (newarr, end); Return Continslen> ¿NotContainlen? Contanslen: nocontainlen; }} // Si no se encuentra no más pequeño que el final, la longitud de retorno es 0 return 0; }}Resultados de ejecución:
6
Mi método puede ocupar mucho espacio porque se abren múltiples matrices nuevas en el medio, pero no creo que sea mucho, no lo he contado. Si hay algo malo, corrígelo.
Para obtener más información sobre los algoritmos de Java, los lectores interesados en este sitio pueden ver los temas: "Estructura de datos Java y tutorial de algoritmo", "Resumen de las puntas de nodo de operación de Java DOM", "Resumen de Java Archivo y TIPS de operación de directorio" y "Summary of Java Cache Operation Tips" TIPS ""
Espero que este artículo sea útil para la programación Java de todos.