vlambda博客
学习文章列表

贪心算法 | leetcode 买卖股票系列


leetcode 买卖彩票的最佳时期

贪心算法。

Leecode121 购买彩票的最佳时期

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

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

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

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

经典的贪心算法,不考虑未来,尽可能地使当前获利最多。

# 只准交易一次
def maxProfit(prices):
"""
:type prices: List[int]
:rtype: int
"""
#贪心算法
n = len(prices)
if n == 0:
return 0

my_buy = -prices[0]
profit = 0

for i in range(1, n):
# 当前值有两种选择,要么买入,要么卖出

# 当前值买入,由于只有一次交易,所花费用为-prices[i]
# 使花费最少,则求max,-2 > -9
my_buy = max(my_buy, -prices[i])

# 当前值卖出,计算收入
profit = max(profit, prices[i] + my_buy)
return profix

可以完成多次交易

你可以完成多笔交易(即在不同天买入和卖出股票多次) 对于股票,你不能在买入股票前卖出股票。

def maxProfit(prices):
n = len(prices)
if n == 0:
return 0
buy = -prices[0]
sell = 0
for i in range(1, n):
# 同样有两种选择,买入或者卖出

# 当前值买入,使得花费最少。
# 最开始sell=0,即花费-prices[i], 之后, 买入的花费为sell - prices[i]
buy = max(buy, sell - prices[i]) # buy都是负值
# 当前值卖出,price[i]减去买入花的钱
sell = max(sell, prices[i] + buy)
return sell

最多完成两次交易

问题变得越来越有意思了,这时需要定义两次买卖的变量。

def maxProfit(prices):
n = len(prices)
if n == 0:
return 0
buy_1 = -prices[0]
sell_1 = 0
buy_2 = -prices[0]
sell_2 = 0

for i in range(1, n):
buy_1 = max(buy_1, -prices[i])
sell_1 = max(sell_1, prices[i] + buy_1)

# 第二次买入必须在第一次卖出之后
buy_2 = max(buy_2, sell_1 - prices[i])
sell_2 = max(sell_2, buy_2 + prices[i])
return max(sell_1, sell_2)

包含一天的冷冻期

含一天的冷冻期,卖出后的一天不能交易,可以多次交易。

这是股票系列问题中目前来看最难的一个,不过有了前面几个问题的思路,这个问题求解起来非常容易。
首先,我们看到问题中提到了三种状态buy、sell和cooldown,那么我们脑中的第一个想法就是通过动态规划来解。

  • 1.考虑index:i天为冷冻期。

那么只能说明index:i-1天卖掉了股票,则第i天的收益和i-1天是一样的。

cooldown[i] = sell[i-1]
  • 2.考虑index:i天卖出

要求利润最大的话,则index:i-1之前就持有股票。一种情况就是index:i-1当天买入了股票,我们在这一天卖出比sell[i-1]获利多;
另一种情况是index:i-1天已经可以卖出,sell[i-1]记录了这种情况。
综上有:

sell[i] = max(sell[i-1], buy[i-1] + prices[i])
  • 3.考虑index:i天买入

要求利润最大的话, 则index:i-1之前就不持有股票。
我们要考虑哪天买,
一种可能是index:i-1天是冷冻期;
另一种可能是index:i-1已经可以买入,buy[i-1]记录这种情况.

buy[i] = max(buy[i-1], cooldown[i-1]-prices[i])
  • 状态的初始化

我们第一天不可能卖出或者冻结,那么这两个

sell[0]=0 cooldown[0]=0;

但是我们第一天可以买入啊,所以:

buy[0]=-prices[0]。

还有一点要注意的就是,我们一定是最后一天卖出或者最后一天冻结利润最大。

完整解法如下:

def maxProfit(prices):
n = len(prices)
if n == 0:
return 0
buy = -prices[0]
sell = 0
cooldown = 0

for i in range(1, n):
buy = max(buy, cooldown - prices[i]) # 如果当前买入,则只能有cooldown转移过来
cooldown = sell
sell = max(sell, buy + prices[i])

return max(sell, cooldown)