Verwenden Sie Java, um den LIS-Algorithmus zu implementieren und das Problem der Formationsbildung zu lösen

Angenommen, es gibt eine Folge: 2,1,3,5. Die längste aufsteigende Teilfolge ist 2,3,5 oder 1,3,5, beide mit einer Länge von 3.

Die Idee des LIS-Algorithmus ist:

Angenommen, es gibt Sequenz a.

① Wenn es nur ein Element gibt, dann ist die Länge der längsten aufsteigenden Teilfolge 1;

② Wenn es zwei Elemente gibt, dann wenn a[1]>a[0] , dann ist die Länge der längsten aufsteigenden Teilfolge 2, und a[1] ist das letzte Element der längsten aufsteigenden Teilfolge, wenn a[1]

③ Wenn es drei Elemente gibt und a[2]>a[0], a[2]>a[1], dann kann a[2] als a[0] verwendet werden. oder a Das letzte Element der längsten aufsteigenden Teilsequenz, in der sich [1] befindet. Welche Sequenz ausgewählt werden soll, hängt davon ab, in welcher Sequenz sich a[0] oder a[1] befindet und welche länger ist.

④ Die Erweiterung auf n Elemente bedeutet, die Länge der längsten aufsteigenden Teilfolge mit a[n] als letztem Element zu betrachten.

Definieren Sie zwei Arrays, eines ist a und das andere ist b.

a speichert die Originaldaten und b[i] speichert die Länge der längsten aufsteigenden Teilsequenz, die mit a[i] endet.

Der Code lautet wie folgt:

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. Übungsgestaltung

Problembeschreibung:

Als ich in der High School war, hatte die Schule Um jeden Morgen die ganze Schule zu organisieren, rennen Lehrer und Schüler zum Training. Sobald der Übungsbefehl ertönt, rennen alle nach unten. Dann stellen sich die kleineren an der Spitze der Reihe auf die Rückseite. Plötzlich hatte der Übungsleiter eines Tages eine Idee und wollte die Formation ändern. Nachdem alle die Treppe hinuntergelaufen waren, wurden alle Schüler nach dem Zufallsprinzip in eine Reihe gestellt, und dann kam der Übungsleiter Für einige Schüler sieht die Körpergröße der verbleibenden Schüler im Team von vorne nach hinten wie eine „Spitzenform“ aus. Man sagt, dass diese Form jedem Glück bringen kann, und ich wünsche Ihnen alles Gute für Ihr Studium. (Beachten Sie, dass nur eine Seite des Berges die Bedingungen erfüllt, z. B. 1,1,2,2,1 alle erfüllen die Bedingungen)

Eingabe:

Die Eingabe kann mehrere Testproben enthalten .
Für jeden Testfall ist die erste Eingabezeile eine Ganzzahl n (1<=n<=1000000), die die Anzahl der einzugebenden Schüler darstellt.
Die zweite Eingabezeile enthält n ganze Zahlen: Sie repräsentieren die Größe des Schülers (cm) (die Größe ist eine positive ganze Zahl, die nicht höher als 200 ist).

Ausgabe:

Geben Sie entsprechend jedem Testfall die Mindestanzahl der Schüler aus, die extrahiert werden müssen.

Beispieleingabe:

6

100 154 167 159 132 105

5

152 152 152 152 152

Beispielausgabe:

0

4

Wenn Sie LIS zur Lösung dieses Problems verwenden, können Sie es sich so vorstellen:

Zunächst einmal , einmal Verwenden Sie LIS rückwärts, um die Länge der längsten aufsteigenden Teilsequenz zu ermitteln, die mit jedem Element endet, kehren Sie dann die Reihenfolge des Arrays um und verwenden Sie dann LIS, um die Länge der längsten aufsteigenden Teilsequenz zu ermitteln, die mit jedem Element endet.

Erhalten Sie zwei Arrays b1, b2.

B1 und b2 werden addiert und dann subtrahiert, was den längsten „Peak“ darstellt.

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;
  }
}

Das Obige ist der gesamte Inhalt des vom Editor bereitgestellten Problems der Verwendung von Java zur Implementierung des LIS-Algorithmus. Ich hoffe, dass es für alle hilfreich sein wird ~

Weitere verwandte Artikel zur Verwendung von Java zur Implementierung des LIS-Algorithmus und der Formationsbildung finden Sie auf der chinesischen PHP-Website!