Cet article décrit la mise en œuvre Java de l'algorithme de sous-séquence le plus long pour les tableaux. Partagez-le pour votre référence, comme suit:
Problème: Compte tenu d'un tableau de longueur n, trouvez la sous-séquence d'auto-inférences monotone la plus longue (pas nécessairement continue, mais l'ordre ne peut pas être gâché). Par exemple: étant donné un tableau de longueur a {1, 3, 5, 2, 4, 6, 7, 8} avec la longueur 8, alors sa séquence d'amplicon monotonique la plus longue est {1, 2, 4, 6, 7, 8} et sa longueur est 6.
Idée 1: Lorsque vous voyez la question au début, beaucoup de gens penseront certainement aux LCS à la première fois. Triez d'abord le tableau dans un nouveau tableau, puis utilisez le nouveau tableau et le tableau d'origine pour trouver des LC pour obtenir la réponse. Beaucoup de gens peuvent imaginer cette solution, donc je n'entrerai pas dans les détails.
Idée 2: Selon l'idée de l'idée 1, vous devez toujours utiliser DP lorsque vous trouvez enfin LCS. Pourquoi n'utilisons-nous pas DP pour le résoudre directement? Pour le tableau ARR, nous traversons le tableau de derrière vers l'avant, et trouvons la plus longue sous-séquence lorsque la sous-séquence se termine par arr[i] , puis prenons la valeur maximale. Vous pouvez obtenir la plus longue sous-séquence de l'ensemble du tableau. Alors, comment trouver la sous-séquence la plus longue se terminant par arr[i] ? Ceci est converti en un problème DP. Pour nécessiter la plus longue sous-séquence de arr[i] , il vous suffit de trouver la plus longue sous-séquence d' arr[i-1] . C'est-à-dire: max{arr[i]}=max{arr[i-1]}+1 .
Code d'implémentation Java:
classe publique 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; // traverse le tableau par derrière pour avancer, et trouvez la longueur de subséquence la plus longue lorsque vous se terminant par arr [i] pour (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 longueur la plus longue de la sous-séquence la plus longue est la longueur du tableau d'origine, // Parce que nous n'avons pas besoin de trouver l'élément de la sous-séquence la plus longue, nous terminons directement la boucle pour réduire le temps au-dessus de la tête si (Max == Maxlen); } System.out.println (max); } public static int dp (int [] arr, int end) {// condition finale récursive if (arr.length == 1) {// Si moins de fin, il est inclus dans la sous-séquence, la longueur de la sous-séquence +1 if (arr [0] <= end) return 1; else return 0; } // Traversé le tableau et trouvez la position de l'élément la plus proche de la fin et <= end i pour (int i = arr.length - 1; i> = 0; i--) {if (arr [i] <= end) {// troncisez le tableau de i, et formez un nouveau tableau vers arr [0] à arrond; System.ArrayCopy (Arr, 0, Newarr, 0, I); // Calculez la sous-séquence la plus longue lors de la contenu ARR [I] et la plus longue subséquence lorsqu'elle ne contenant pas ARR [i], respectivement, et prends la valeur maximale int contientLen = dp (newarr, arr [i]) + 1; int notContainlen = dp (newarr, end); return contientLen> notContainlen? CONTAINSLEN: NotContainlen; }} // Si pas plus petit que la fin n'est trouvé, la longueur de retour est 0 Retour 0; }}Résultats en cours:
6
Ma méthode peut prendre beaucoup d'espace car plusieurs nouveaux tableaux sont ouverts au milieu, mais je ne pense pas que ce soit beaucoup - - je ne l'ai pas compté. S'il y a quelque chose de mal, veuillez le corriger.
Pour plus d'informations sur les algorithmes Java, les lecteurs qui sont intéressés par ce site peuvent afficher les sujets: "Structure de données Java et tutoriel d'algorithme", "Résumé des conseils de nœud de Dom Operation Java", "Résumé du fichier Java et des conseils d'opération de répertoire" et "Résumé des conseils d'opération Java Cache"
J'espère que cet article sera utile à la programmation Java de tous.