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
Vous devez vous connecter pour publier un commentaire.
Commencer à partir du dernier élément et de le déplacer vers l'arrière. garder en mémoire la partie la plus importante s'est produite jusqu'à présent.
pour chaque élément se soustraire au max et gardez-le à la position correspondante.
Aussi, vous pouvez garder un élément à stocker le max de la différence et de donner à la sortie tout de suite.
O(n), O(1) de l'espace.
Dhandeep de l'algorithme est bonne et Vivek pour la traduction du code Java fonctionne!
Aussi, nous pouvons également analyser le tableau normalement et pas dans le sens inverse:
Merci @Dhandeep Jain pour la réponse. Il y a la version de java:
Je propose que la plus grande différence est toujours entre le plus grand nombre et le plus petit nombre avant ou entre le nombre le plus petit et le plus grand nombre par la suite. Ceux-ci peuvent être déterminés dans le temps linéaire.
D'abord trouver la différence entre les éléments adjacents de la matrice et de stocker toutes les différences dans les services auxiliaires de la matrice de diff[] de taille n-1. Maintenant ce problèmes se transforme en trouver le maximum de la somme subarray de cette différence de tableau.
Ruby solution:
Je suis sûr que cela devrait résoudre votre problème: