Come posso trovare in modo efficiente il più grande intervallo positivo in un array non orientato? [duplicare

Question

Questa domanda ha già una risposta qui:

• Trovare una soluzione O (n) a: differenza massima di domanda di array [chiusa 2 risposte

Dato un insieme di valori come [4, 8, 1, 5, 2, 6, 9, 2, 3, 5, 11, 9], come posso trovare il più grande intervallo positivo tra due di essi? Ad esempio in quello che ho appena elencato, l'indice da 0 a indice 1 ha un intervallo di 4 perché 8 - 4 = 4. Ma il più grande intervallo positivo è tra l'indice 2 e l'indice 10, perché 11 - 1 = 10.

Vedo che c'è un modo per farlo in tempo lineare, ma non riesco a capire di cosa si tratta. La soluzione N^2 Brute Force è semplice, ma voglio capire il modo migliore.

---

Per essere chiari, il più grande intervallo positivo in [20, 1, 4] sarebbe 3, non 19, perché 20 -> 1 è un intervallo di -19.

---

La soluzione che vorrei avanzare è quella di tradurre l'array in tempo lineare in una serie di differenze, ad esempio [20, 1, 7, 4, 2] diventa [0, -19, 6, -3, -2] e quindi Usa l'algoritmo di Kadane per trovare la massima sottosequenza contigua. La più grande sottosequenza sarebbe 6 Da solo, implicando indici 1 e 2 hanno fornito la risposta.