Maksymalna różnica w tablicy.

0

W dniach 1,2,...,n cena produktu wynosiła odpowiednio p(1),p(2),..p(n) złotych. Napisz algorytm, który zwróci parę (i,j) tzn. dzień i, w którym opłaca się go najbardziej kupić, a j to dzień w którym go sprzedać (czyli po prostu p(j)-p(i) ma być maksymalne). Oczywiście j>i.

Bruteforce na O(n^2) jest banalne, natomiast coś O(n logn)?
Myślałem nad 2 tablicami - z kosztami i dniami - posortowaniem tego po kosztach, co sortuje także dni w tablicy, ale co z tym potem zrobić..

5

Nie wystarczy znaleźć min oraz max (czyli O(n))?

1

lecisz od początku do końca, porównujesz z min, max, i jeżeli znajdziesz nowe lokalne max porównujesz z ostatnio znalezionym max-min

1 użytkowników online, w tym zalogowanych: 0, gości: 1