¿Algoritmo de "diferencia máxima" de matriz que se ejecuta en O (n)?
Dada una matriz de N enteros, ordene la matriz y encuentre los 2 números consecutivos en la matriz ordenada con la diferencia máxima. Ejemplo: en la entrada [1,7,3,2] salida 4 (la matriz ordenada es [1,2,3,7], y la diferencia máxima es 7-3 = 4).
El algoritmo A se ejecuta en tiempo O (NlogN).
Necesito encontrar un algoritmo idéntico en función al algoritmo A, que se ejecuta en tiempo O (N).
ACTUALIZAR:
Solución:http://cgm.cs.mcgill.ca/~godfried/teaching/dm-reading-assignments/Maximum-Gap-Problem.pdf