Wie man alle am längsten abnehmenden Sequenzen ausgibt

Question

Angenommen, ich habe eine Reihe von Ganzzahlen mit einer Länge $ n $. Wie kann ich alle am längsten abnehmenden Sequenzen ausgeben? (Eine Subsequenz besteht aus Elementen des Arrays, die nicht aufeinanderfolgend sein müssen, zum Beispiel $ (3.2,1) $ ist eine abnehmende Subquenz von $ (7,3,5,2,0,1).) Ich weiß, wie man die Länge der längsten abnehmenden Sequenzen berechnet, aber nicht, wie man alle am längsten abnehmenden Sequenzen meldet.

Pseudocode wird hilfreich sein.

Answer 1

Betrachten Sie die folgende Sequenz als Ihre Eingabe:

$$ N, N-2, N-1, N-3, N-5, N-4, N-6, N-8, N-7, N-9, ...., N-3 Cdot K - 2, N -3 CDOT K - 1, N -3 CDOT K - 3, .... $$

Der Einfachheit halber nimmt $ n = 3 cdot t + 1 $ an, die längste abnehmende Subsequenzlänge $ t $ und die Anzahl der abnehmenden Subsequence der Länge $ t $ 2^t $.

Die Anzahl der vglückbaren Lösungen ist also $ theta (2^{n/3}) $. Aber warum ist es so, einfach mit DAG modellieren, achten Sie darauf, dass es einen Vorteil von $ A $ → $ B $ gibt, wenn $ A> B $ und $ B $ nach $ a $ in Originalsequenz ist.

Da die Ausgangsgröße exponentiell sein kann, ist die beste Wahl, DAG zu erstellen und alle längsten Wege in DAG oder auf andere Weise zu finden, die alle akzeptablen Arten aufzählen.

Answer 2

-E eine rekursive Helferfunktion

    list form_longest_sublist_from(list array,list buffer,from) 
            add array[from] to buffer

            list ret as copy of buffer
            from i = from - 1 to -1 step -1
                   if last buffer > array[i] 
                   list sbuffer
                   sbuffer = form_longest_sublist_from(array,buffer,i);
                   if length sbuffer > length ret
                      ret = sbuffer;
                   endif
                endif
            endfor
            return ret;
    endfunc

• Der Algorithmus zur Verwendung der Funktion

  list of lists arrayoflongestlist
      list buffer;
      from i = length array - 1 to -1 step -1
          clear buffer
          add array[i] to buffer
          from x = i - 1 to -1 step -1
              if(array[x] < last buffer
                  list sbuffer;
                  sbuffer = form_longest_sublist_from(array,buffer,x);
                  if length sbuffer > length buffer)
                      buffer = sbuffer;
                              endif
              endif
          endfor
              if length arrayoflongestlist > 0
                     if length (last arrayoflongestlist) < length buffer
                              clear arrayoflongestlist
                              add buffer to arrayoflongestlist
                     endif
                     else if length (last arrayoflongestlist) == length buffer
                  add buffer to arrayoflongestlist
              endif
  
                     if length (last arrayoflongestlist) > i)
                  break;
          else
              add buffer to arrayoflongestlist
          endif
      endfor
  

Ich habe den gesamten Algorithmus im Grunde genommen so neu gestaltet, um das Problem zu passen.

Die Grundidee besteht darin, von jedem möglichen Punkt (jedes Element) im Array aus zu beginnen und alle möglichen abnehmenden Sublisten zu formen Bevor Sie von diesem Zeitpunkt an beginnen und dann die Rekursionen für die am längsten zurückgegebene Liste filtern.

Meine möglichen schlimmsten/besten Szenarien, die zuvor erwähnt wurden, sind in Anbetracht dieses Algorithmus nicht richtig.

Answer 3

Speichern Sie für jede abnehmende Sequenz die Anfangspositionen in einem anderen Array.

for( i = 0; i < n-1; i++ ) {
    if ( a[i] > a[i+1] ) {
        temp[j++] = i;
        while( a[i] > a[i+1] ) {
            i++;
        }
        temp[j++] = i;
    }
}

Jetzt enthält die Array -Temperatur anfängliche und endgültige Positionen aller abnehmenden Sequenzen nacheinander. Dann drucken Sie sie aus