LeetCode 121. 买卖股票的最佳时机
2022-08-17 本文已影响0人
草莓桃子酪酪
题目
给定一个数组 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]
