unreasonably effective

link

Profit is (sell-buy). For each possible buy, we find the best sell (max day’s price) in the future.

Time: , space: .

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_profit = float('-inf')
        for i, buy in enumerate(prices[0:len(prices)-1]):
            best_sell = max(prices[i+1:])
            max_profit = max(max_profit, best_sell-buy)
        return max(max_profit, 0)

Going through the days in sequence, we keep track of the best_buy; therefore, the minimum price seen so far. Everyday we consider selling and to compute the max_profit for that day we retrospectively use the best_buy. We may be buying and selling on the same day. Strictly speaking, this is not allowed. However, this would happen only if there isn’t a better buy in the past. In which case, the “correct” max_profit would have been negative. Since, by definition max_profit is at least 0, our answer would still be correct.

Time: , space: .

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_profit = float('-inf')
        best_buy = float('inf')
        for price_today in prices:
            best_buy = min(best_buy, price_today)
            max_profit = max(max_profit, price_today - best_buy)
        return max(max_profit, 0)