Trouver la plus grande différence possible dans un tableau avec l'entier plus petit se produisant plus tôt

C'est une question d'entrevue:

Trouver la plus grande différence possible dans un tableau d'entiers, de sorte que le plus petit entier se produit plus tôt dans le tableau.

Contrainte:
Les numéros ne sont pas uniques.
La gamme est Entier gamme de java. (ou toute autre langue)

Exemple:

d'entrée 1: {1, 100, 2, 105, -10, 30, 100}

La plus grande différence est entre 10 et 100 -> 110 (ici, -10, c'est à la 5e index et 100 est à la 7ème index)

d'entrée 2: {1, 100, 2, 105, -10, 30, 80}

La plus grande différence est entre 1 et 105 -> 104 (ici 1 est le 1er indice 105 et est au 4ème indice)

Solution Possible:

Une approche est de vérifier pour toutes les différences possibles et de garder une trace de la plus grande différence trouvée jusqu'à maintenant, O(n^2) complexité.

cela peut-il faire mieux que O(n^2)?

source d'informationauteur Vivek