BinarySearch 0788 Turtle of Wall Street

Problem statement

https://binarysearch.com/problems/Turtle-of-Wall-Street/

Solution

Keep cumulative maximums of prefixes, then for each stock we know how expensive we can sell it.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, A):
        acc = list(accumulate(A[::-1], max))[::-1]
        return sum(x - y for x, y in zip(acc, A))