Biorąc pod uwagę tablicę N liczb całkowitych, posortuj tablicę i znajdź 2 kolejne liczby w posortowanej tablicy z maksymalną różnicą. Przykład - na wejściu [1,7,3,2] wyjście 4 (posortowana tablica to [1,2,3,7], a maksymalna różnica to 7-3 = 4).

Algorytm A działa w czasie O (NlogN).

Muszę znaleźć algorytm identyczny pod względem funkcji z algorytmem A, który działa w czasie O (N).

AKTUALIZACJA:

Rozwiązanie:http://cgm.cs.mcgill.ca/~godfried/teaching/dm-reading-assignments/Maximum-Gap-Problem.pdf