Comment puis-je trouver efficacement le plus grand intervalle positif dans un tableau non trié? [dupliquer

Question

Cette question a déjà une réponse ici:

• Trouver une solution O (n) à: Différence maximale de la question du tableau des paires [fermé 2 réponses

Étant donné un ensemble de valeurs comme [4, 8, 1, 5, 2, 6, 9, 2, 3, 5, 11, 9], comment puis-je trouver le plus grand intervalle positif entre deux d'entre eux? Par exemple, dans celui que je viens de répertorier, l'index 0 à l'index 1 a un intervalle de 4 car 8 - 4 = 4. Mais le plus grand intervalle positif se situe entre l'indice 2 et l'indice 10, car 11 - 1 = 10.

Je peux voir qu'il existe un moyen de le faire en temps linéaire, mais je ne peux pas comprendre ce que c'est. La solution de force brute n ^ 2 est simple, mais je veux comprendre la meilleure façon.

---

Pour être clair, le plus grand intervalle positif en [20, 1, 4] serait 3, pas 19, car 20 -> 1 est un intervalle de -19.

---

La solution que je proposerais est de traduire le tableau en temps linéaire à un tableau de différences, par exemple [20, 1, 7, 4, 2] [0, -19, 6, -3, -2], puis Utilisez l'algorithme de Kadane pour trouver la subséquence contigu maximale. La plus grande sous-séquence serait 6 En soi, les indices 1 et 2 impliquant les indices 1 et 2 ont fourni la réponse.