Mindestanzahl von Operationen, um ein Array sortiert zu machen

Question

Ich habe versucht, this Problem auf spoj, nicht in der Lage, mit dem richtigen Ansatz zu kommen. Was ist der richtige Algo, um das Problem zu lösen?

Answer 1

Sie sollten die längste aufeinanderfolgende ansteigende Untersequenz finden, die in O (n log n) (durch Sortierung des Arrays) durchgeführt werden kann. Danach ist die Anzahl der erforderlichen Änderungen N - longest consecutive increasing subsequence. Beachte, dass ich mit "konsekutiv" meine Ordnung in sortierter Anordnung meine.

Beispiel:

1 7 6 2 5 4 3 => 1-2-3 am längsten ist in Folge zunehmende Subsequenz, Anzahl von Zügen erforderlich ist 4.

1 6 4 3 5 2 7 => 1-2 oder 4-5 oder 6-7 ist längste Subsequenz konsekutiver Erhöhung zu beachten, dass 1-4-5-7 ist längst zunehmende Subsequenz aber Anzahl von Zügen erforderlich ist 5 nicht 3.

Warum das funktioniert:

besten Algorithmus nicht hat einige von einem Artikel Orte ändert, rufen größte Teilfolge ohne Änderungen als X, man wird nicht die Position der X Elemente zueinander während Operationen zusammenhängen ändern, so sollten sie in Erhöhungsmodus sortiert werden. Da Sie jedoch nur einige Elemente im ersten oder letzten Array verschoben haben, können Sie keine Elemente zwischen X Elemente einfügen (wir haben angenommen, dass X die größte unveränderte Teilsequenz während der Operationen ist). Daher sollte keine Lücke zwischen X bestehen Artikel. Daher sollten sie in sortiertem Format sortiert und fortlaufend sortiert werden.

So Anzahl der erforderlichen Änderungen könnte nicht kleiner sein als die N- length of X, aber es ist auch nicht schwer, Ihre Arbeit mit N-length of X operation zu tun.