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ć..