leetcode-0121 买卖股票的最佳时机

[meishaoming]

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

解法一

审完题的第一个想法：

对每个元素，算一遍它后边每一次卖出的获利，保存最大值。

这样，对第一个元素，要算 n-1 次， 对第二个元素，要算 n-2 次 ... 总共要算 ((n-1)^2)/2 次，时间复杂度为 O(n^2)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        i = j = 0
        profit = 0
        for i in range(len(prices)):
            for j in range(i+1, len(prices)):
                profit = max(profit, prices[j] - prices[i])
        return profit

解法二

第 n 天的价格为 p(n)，前面 n-1 天的最低价格为 min(n-1)

第 n 天的利润 f(n) = p(n) - min(n-1)

所以，自底向上，算出每天出售的最大获利，遍历一次就可以算出结果。

前 n 天的最大获利 = max(前 n-1 天的最大获利, 当天的获利)

其中，当天的获利 = 当前的价格 - （前 n-1 天最低的价格）

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) == 0:
            return 0
        max_profix = 0
        min_value = prices[0]
        for x in prices[1:]:
            min_value = min(min_value, x)
            max_profix = max(max_profix, x-min_value)
        return max_profix