Wenn Sie ein Array mit N ganzen Zahlen erhalten, sortieren Sie das Array und suchen Sie die 2 aufeinander folgenden Zahlen im sortierten Array mit der maximalen Differenz. Beispiel - am Eingang [1,7,3,2] wird 4 ausgegeben (das sortierte Array ist [1,2,3,7] und die maximale Differenz beträgt 7-3 = 4).

Algorithmus A läuft in der Zeit O (NlogN).

Ich muss einen Algorithmus finden, der in seiner Funktion mit dem Algorithmus A identisch ist und in der O (N) -Zeit abläuft.

AKTUALISIEREN:

Lösung:http://cgm.cs.mcgill.ca/~godfried/teaching/dm-reading-assignments/Maximum-Gap-Problem.pdf