Leetcode 121：买卖股票的最佳时机（最详细的解法！！！）

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

解题思路

这个问题非常简单，我们可以通过递归很快速的解决这个问题。假设我们的最后结果是result，那么我们result来源于两种选择策略

• 包含prices[0]
• 不包含prices[0]

如果我们包含prices[0]的话，也就是prices[0]买入，那么我们只要遍历prices[1:]找到max(i-prices[0])即可（其中i为prices[1:]中的每个元素）。对于不包含prices[0]的问题就更简单了，我们只要通过self.maxProfit(prices[1:])返回即可。

class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        result = 0
        if not prices:
            return result

        for i in prices[1:]:
            if i > prices[0]:
                result = max(result, i - prices[0])

        return max(result, self.maxProfit(prices[1:]))

对于这个问题，我们同样可以通过记忆化搜索的策略进行优化。

class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        mem = [-1]*len(prices)
        return self._maxProfit(prices, 0, mem)

    def _maxProfit(self, prices, index, result):
        if index >= len(prices):
            return 0

        if result[index] != -1:
            return result[index]

        for i in prices[index+1:]:
            if i > prices[index]:
                result[index] = max(result[index], i - prices[index])

        result[index] = max(result[index], self._maxProfit(prices, index+1, result))
        return result[index]

同样我们可以使用动态规划解决这个问题。转移方程就是

• $f(i) = max(f(i), j - prices[i]) \ \ \ \ for \ i \in prices[i+1:]$f(i)=max(f(i),j−prices[i])    for i∈prices[i+1:]
• $f(i)=max(f(i), f(i+1))$f(i)=max(f(i),f(i+1))

class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        result = [0]*len(prices)
        if not prices:
            return 0
        
        for i in range(len(prices)-2, -1, -1):
            for j in prices[i+1:]:
                if j > prices[i]:
                    result[i] = max(result[i], j - prices[i])
            result[i] = max(result[i], result[i+1])

        return result[0]

但是这个问题最简单的处理思路是贪心算法。我们遍历prices这个数组，假设我们遍历到i，这个时候我们可以知道prices[:i]中的最小值buy，那么我们也会知道prices[:i]的最小差价（每次计算max(prices[i]-buy)）。

class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        result, buy = 0, float('inf')
        for price in prices:
            if buy > price:
                buy = price
            
            if result < price - buy:
                result = price - buy

        return result

其实这种问题的难点在于判断是不是可以通过贪心解决。

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题，希望大家指出！！！