Annettuna on osakkeen hinta n päivän aikana. Voit ostaa osakkeen tiettynä päivänä ja myydä sen samana tai myöhempänä päivänä.
Tehtäväsi on laskea kullekin päivälle suurin tuotto, jonka olisit voinut saada myymällä osakkeen kyseisenä päivänä.
Esimerkiksi kun hinnat ovat [3,2,3,5,1,4], sinun tulee muodostaa lista [0,0,1,3,0,3]. Esimerkiksi neljännen päivän kohdalla suurin tuotto on 3, koska olisit voinut ostaa osakkeen hintaan 2 ja myydä sen hintaan 5.
Toteuta tiedostoon stock.py funktio find_profits, jolle annetaan parametrina lista osakkeen hinnoista. Funktion tulee palauttaa yllä olevan kuvauksen mukainen lista.
Sinun tulee toteuttaa tehokas ratkaisu, jonka aikavaativuus on O(n). Et voi esimerkiksi käydä jokaisen päivän kohdalla kaikkia aiempia päiviä läpi, vaan sinun tulee määrittää suurin tuotto tehokkaasti.
Tehtäväpohjan viimeisessä testissä osakkeen hinnat ovat [1,2,\dots,10^5]. Funktiosi tulee toimia tehokkaasti tässäkin tapauksessa.
def find_profits(prices):
# TODO
if __name__ == "__main__":
print(find_profits([1, 2, 3, 4])) # [0, 1, 2, 3]
print(find_profits([4, 3, 2, 1])) # [0, 0, 0, 0]
print(find_profits([1, 1, 1, 1])) # [0, 0, 0, 0]
print(find_profits([2, 4, 1, 3])) # [0, 2, 0, 2]
print(find_profits([1, 1, 5, 1])) # [0, 0, 4, 0]
print(find_profits([3, 2, 3, 5, 1, 4])) # [0, 0, 1, 3, 0, 3]
prices = list(range(1, 10**5+1))
print(find_profits(prices)[:5]) # [0, 1, 2, 3, 4]