Annettuna on osakkeen hinta n päivän ajalta. Tehtäväsi on selvittää, mikä olisi ollut suurin mahdollinen tuotto, jos olisit voinut ostaa ja myydä osakkeen enintään kahdesti.
Sinulla saa olla hallussasi kerrallaan enintään yksi osake. Lisäksi jos ostat osakkeen toisen kerran, välissä täytyy olla ainakin yksi päivä, jolloin sinulla ei ollut osaketta.
Algoritmin aikavaativuuden tulee olla O(n).
Toteuta tiedostoon trading.py funktio find, joka palauttaa halutun tuloksen.
def find(t):
# TODO
if __name__ == "__main__":
print(find([1,5,2,1,5])) # 8
print(find([1,5,1,5])) # 4
print(find([1,2,3,4,5])) # 4
print(find([5,4,3,2,1])) # 0
print(find([4,2,5,8,7,6,1,2,5,1])) # 10
Selitys: Kun hinnat ovat [1,5,2,1,5], tuotto 8 saadaan toistamalla kahdesti osto ja myynti hintaan 1 ja 5. Kun hinnat ovat [1,5,1,5], tämä ei ole mahdollista, koska myynnin ja oston välissä tulee olla ainakin yksi päivä. Silloin voit saada vain tuoton 4 ostamalla ja myymällä osakkeen kerran.