LIS zu finden in einer Reihe von benutzerdefinierten Objekten basierend auf mehr als ein Feld

Question

Das Codierung Interview Cracking (5. Aufl): 11 Chp, Ques 7

Frage: Ein Zirkus einen Turm Routine ist die Gestaltung von Menschen aus Sie stehen sich auf den Schultern. Aus praktischen und ästhetischen Gründen muss jede Person sowohl kürzer als auch leichter als die Person unter ihm sein. Berücksichtigen Sie die Größe und das Gewicht jeder Person im Zirkus und schreiben Sie eine Methode, um die größtmögliche Anzahl von Personen in einem solchen Turm zu berechnen.

Meine Zweifel:

• In der Lösung in dem Buch klar im Text erwähnt wird , dass die Elemente sortiert wird die Lösung zu trivial machen, warum dann Elementen zunächst im Code sortiert wurden?

Wenn die Elemente müssen nicht in der gleichen (relativen), um zu bleiben, dann wir das Array einfach sortieren würde. Dies macht das Problem zu trivial, also nehmen wir an, dass die Elemente in der gleichen relativen Reihenfolge bleiben müssen. Hier

ist der Code aus dem Buch, wo Sortierung erfolgt ist (die ersten drei Zeilen des Codes):

ArrayList<HtWt> getIncreasingSequence(ArrayList<HtWt> items)  
    {  
     Collections.sort(items);  
     return longestIncreaingSequence(items);  
    } 

Answer 1

Die vorgeschlagene Lösung aus 2 Schritten besteht:

1. sortieren nach Gewicht
2. finden Sie die am längsten zunehmende Unterfolge auf den Höhen

Der zitierte Satz ist nicht relativ zum ersten Schritt, sondern zum zweiten Schritt (Finden der längsten aufsteigenden Teilfolge) und erklärt, dass wir die Höhen nicht einfach sortieren können, weil wir ihre Reihenfolge nicht ändern können, da sie bereits existieren sortiert nach ihren Gewichten.

Werfen Sie einen Blick auf dieses Beispiel mit 5 Personen:

weights: 4 5 1 7 2 
heights: 6 3 5 4 1 

Ergebnis nach Schritt 1 (Gewichtssortierung):

weights: 1 2 4 5 7 
heights: 5 1 6 3 4 

Jetzt, in den Höhen suchen wir, dass die längste sehen steigende Subsequenz ist 1 3 4, die uns sagen, dass die Lösung besteht aus 3 Menschen. Um dieses Ergebnis zu erhalten, können wir nicht nur nach Höhen sortieren, da sie bereits nach ihrem Gewicht sortiert sind ...

... müssen die Elemente in der gleichen relativen Reihenfolge bleiben.

Also müssen wir stattdessen einen am längsten zunehmenden Subsequenzalgorithmus verwenden.