You are given the price of a stock during a period of days. As in the earlier task, your task is to compute for each day the largest profit you could have achieved by selling the stock on that day.
The difference to the earlier task is that in addition to the sales profit you can gain a dividend on each day. When you buy on the day and sell on the day , the dividend is .
For example, when the prices are , the list of profits is . For example, when selling on the fifth day, the largest profit is , because you could have bought the stock on the second day at the price and then sold it at the price . Thus the sales profit is and the dividend is for a total profit of .
In a file dividend.py
, implement the function find_profits
that takes a list of prices as a parameter, and returns the list of profits. As before, you need an efficient solution with a time complexity .
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]