CSES - Dividend

You are given the price of a stock during a period of nn 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 aa and sell on the day bb, the dividend is bab-a.

For example, when the prices are [3,2,3,5,1,4][3,2,3,5,1,4], the list of profits is [0,0,2,5,2,6][0,0,2,5,2,6]. For example, when selling on the fifth day, the largest profit is 22, because you could have bought the stock on the second day at the price 22 and then sold it at the price 11. Thus the sales profit is 12=11-2=-1 and the dividend is 52=35-2=3 for a total profit of 1+3=2-1+3=2.

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 O(n)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]