Utiliser Java pour implémenter l'algorithme LIS et résoudre le problème de la formation

Supposons qu'il existe une séquence : 2,1,3,5. La sous-séquence ascendante la plus longue est 2,3,5 ou 1,3,5, toutes deux d'une longueur de 3.

L'idée de l'algorithme LIS est la suivante :

Supposons qu'il existe une séquence a.

① S'il n'y a qu'un seul élément, alors la longueur de la sous-séquence ascendante la plus longue est de 1

② S'il y a deux éléments, alors si a[1]>a[0] ; , alors la longueur de la sous-séquence ascendante la plus longue est 2, et a[1] est le dernier élément de la sous-séquence ascendante la plus longue ; si a[1]

③ S'il y a trois éléments, alors si a[2]>a[0], a[2]>a[1], alors a[2] peut être utilisé comme a[0] ou a Le dernier élément de la sous-séquence ascendante la plus longue où se trouve [1]. La séquence à choisir dépend de la séquence dans laquelle se trouve a[0] ou a[1] qui est la plus longue.

④ S'étendre à n éléments signifie regarder la longueur de la sous-séquence ascendante la plus longue avec a[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 sous-séquence ascendante la plus longue se terminant par a[i].

Le code est le suivant :

class Lmax{
    
  public static void Lmax(int[] a,int[] b){
      
    b[0]=1;             
          
    for(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];   //记录下元素数值比a[i]小的但是对应子序列最长的子序列长度
        }
      }
        
      b[i]=countmax+1;     //a[i]对应的最长子序列长度是
    }
          
  }
    
}

2. Formation aux exercices

Description du problème :

Quand j'étais au lycée, l'école avait pour organiser toute l'école chaque matin. Les professeurs et les élèves de l'école courent pour faire de l'exercice. Chaque fois que l'ordre est donné, tout le monde commence à courir en bas. Ensuite, les plus petits s'alignent en tête de file et les plus grands s'alignent en tête. dos. Soudain, un jour, le responsable de l'exercice a eu une idée et a voulu changer la formation. C'est-à-dire qu'après que tout le monde ait descendu les escaliers, tous les élèves ont été placés au hasard dans une rangée, puis le responsable de l'exercice. l'exercice a été tiré de l'équipe. Pour certains élèves, la taille des autres élèves de l'équipe ressemble à une forme de « pic » vue d'avant en arrière, montant d'abord puis descendant. On dit que cette forme peut porter chance à tout le monde, et je vous souhaite le meilleur dans vos études. (Remarque : un seul côté de la montagne remplit les conditions, par exemple 1,1,2,2,1 remplissent tous les conditions)

Entrée :

L'entrée peut contenir plusieurs échantillons de test .
Pour chaque cas de test, la première ligne de saisie est un entier n (1<=n<=1000000) : représentant le nombre d'étudiants à saisir.
La deuxième ligne de saisie comprend n nombres entiers : représentant la taille de l'élève (cm) (la taille est un entier positif ne dépassant pas 200).

Sortie :

Correspondant à chaque cas de test, affichez le nombre minimum d'étudiants qui doivent être extraits.

Exemple d'entrée :

6

100 154 167 159 132 105

5

152 152 152 152 152

Exemple de sortie :

0

4

Lorsque vous utilisez LIS pour résoudre ce problème, vous pouvez y penser comme ceci :

Tout d'abord , il était une fois Utilisez LIS à l'envers pour trouver la longueur de la sous-séquence ascendante la plus longue se terminant par chaque élément, puis inversez l'ordre du tableau, puis utilisez LIS pour trouver la longueur de la sous-séquence ascendante la plus longue se terminant par chaque élément.

Obtenez deux tableaux b1, b2.

L'addition correspondante de b1 et b2, puis la soustraction de celui répété est la « montagne » la plus longue.

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];           //原始数组
    int []ar = new int[n];          //逆序数组
    Scanner in = new Scanner(System.in);
      
    for(int i=0;i<n;i++){
      a[i]=in.nextInt();
    }     
    int[] b1 = new int[n];
    @SuppressWarnings("unused")
    int[] b2 = new int[n];
    Lmax.Lmax(a, b1);
    ar=reverse.reverse(a);     
  
    Lmax.Lmax(ar, b2);       //求解逆序数组的最长上升子序列
  
    b2=reverse.reverse(b2);     //将逆序数组的最长上升子序列逆序以便和原始数组的最长上升子序列对应相加
      
    re = result.result(b1, b2);
    System.out.print(re);
  }
  
}<br><br><br><br>

class result{
  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;    //对应相加最长的再减去重复的一个人
    return 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 formation apporté par l'éditeur. J'espère que cela sera utile à tout le monde. Veuillez prendre en charge le site Web PHP chinois. ~

Pour plus d'articles sur l'utilisation de Java pour implémenter l'algorithme LIS et la formation de formation, veuillez faire attention au site Web PHP chinois !