Problem

Solution

Intuition

This problem requires finding the maximum profit within the array. The current maximum profit is the current price minus the current previously seen low.

Approach

We only need to save two variables in order to make this algorithm work. The current resulting maximum profit and the currently known low. As we scan through the array, if we find a higher profit, we update the result, and if we’ve found a new low, we save that for future profit calculations.

Complexity

• Time complexity: $O(n)$ as we do a single loop through the array with constant time operations every iteration.
• Space complexity: $O(1)$ as we only save two variables.

Code

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        res = 0
        lowest = prices[0]

        for price in prices:
            res = max(price - lowest, res)
            lowest = min(lowest, price)
        return res