Osinko

Annettuna on osakkeen hinta $n$ päivän aikana. Kuten aiemmassa tehtävässä, sinun tulee laskea kullekin päivälle suurin tuotto, jonka olisit voinut saada myymällä osakkeen kyseisenä päivänä.

Kuitenkin erona aiempaan saat myyntituoton lisäksi myös päivittäin osinkoa. Kun ostat osakkeen päivänä $a$ ja myyt sen päivänä $b$, osingon suuruus on $b-a$.

Esimerkiksi kun hinnat ovat $[3,2,3,5,1,4]$, sinun tulee muodostaa lista $[0,0,2,5,2,6]$. Esimerkiksi viidennen päivän kohdalla suurin tuotto on $2$, koska olisit voinut ostaa toisena päivänä osakkeen hintaan $2$ ja myydä sen sitten hintaan $1$. Tässä myyntituotto on $1-2=-1$ ja osingon suuruus on $5-2=3$, joten kokonaistuotto on $-1+3=2$.

Toteuta tiedostoon dividend.py funktio find_profits, jolle annetaan parametrina lista osakkeen hinnoista. Funktion tulee palauttaa yllä olevan kuvauksen mukainen lista. Kuten aiemminkin, tehtäväsi on toteuttaa tehokas ratkaisu, jonka aikavaativuus on $O(n)$.

def find_profits(prices):
    # TODO

if __name__ == "__main__":
    print(find_profits([1, 2, 3, 4])) # [0, 2, 4, 6]
    print(find_profits([4, 3, 2, 1])) # [0, 0, 0, 0]
    print(find_profits([1, 1, 1, 1])) # [0, 1, 2, 3]
    print(find_profits([2, 4, 1, 3])) # [0, 3, 1, 4]
    print(find_profits([1, 1, 5, 1])) # [0, 1, 6, 3]
    print(find_profits([3, 2, 3, 5, 1, 4])) # [0, 0, 2, 5, 2, 6]

    prices = list(range(1, 10**5+1))
    print(find_profits(prices)[:5]) # [0, 2, 4, 6, 8]