LeetCode 121. 买卖股票的最佳时机

题目

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

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

方法：暴力解法

计算每天若要选择卖出的话的最大利润，通过两个循环实现

class Solution(object):
    def maxProfit(self, prices):
        result = 0
        for i in range(1, len(prices)):
            for j in range(i):
                if prices[i] - prices[j] > result:
                    result = prices[i] - prices[j]
        return result

※ 超出时间限制

方法：贪心算法

• result 表示当前利润的最大值，low 表示当前遇到的价格最小值
• 通过循环实现对两个参数的记录

class Solution(object):
    def maxProfit(self, prices):
        result = 0
        low = float('inf')
        for i in range(len(prices)):
            low = min(low, prices[i])
            result = max(result, prices[i] - low)
        return result

方法：动态规划

• dp[i][0] 表示第 i 天持有股票所拥有的最多现金（负数），dp[i][1] 表示第 i 天不持有股票所拥有的最多现金
• 初始化。dp[0][0] 即第一天持有股票所拥有的最多现金，即第一天买入股票，那么此时应赋值 -prices[0]；dp[0][1]即第一天不持有股票所拥有的最多现金，即第一天不买入股票，那么此时赋值 0
• 循环记录。dp[i][0] 有两种可能性：第 i-1 天就持有股票 dp[i-1][0]，第 i-1 天并未持有股票但在第 i 天买入股票 -prices[i]，取这两种可能的较大值。dp[i][1] 有两种可能：第 i-1 天就未持有股票 dp[i-1][1]，第 i-1 天持有股票但在第 i 天卖出股票 prices[i] + dp[i-1][0]，取这两种可能的较大值

class Solution(object):
    def maxProfit(self, prices):
        dp = [[0] * 2 for row in range(len(prices))]
        dp[0][0], dp[0][1] = -prices[0], 0
        for i in range(1, len(prices)):
            dp[i][0] = max(dp[i-1][0], -prices[i])
            dp[i][1] = max(dp[i-1][1], prices[i] + dp[i-1][0])
        return dp[-1][1]

参考

代码相关：https://programmercarl.com/0121.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BA.html