class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if len(prices) <= 1:
return 0
elif len(prices) ==2:
return prices[1]-prices[0] if prices[1]>prices[0] else 0
# dp 动态规划适用的条件是len(prices)>=3
# 注意这里必须要dp1[0] = 0
# dp 状态分析
# dp1[i] 表示在位置 i 卖股票最大的收益
# dp[0] 不可能购买购票, 其实这个位置是不可达的位置
dp1 = [0]*len(prices)
min_p = prices[0]
for i in range(1, len(prices)):
dp1[i] = max(dp1[i-1], prices[i]-min_p)
min_p = min(min_p, prices[i])
# 注意这里的必须要dp2[-1] = 0
# 因为dp2[i]的状态表示的在i 位置购买股票的最大收益.
# 你显然不能在 dp2[-1]购买股票, 这个位置不可达
# 因为表示在 i 位置购买收益, 所以得倒序推导
dp2 = [0]*len(prices)
max_p = prices[-1]
for i in range(len(prices)-2, -1, -1):
dp2[i] = max( dp2[i+1], max_p - prices[i] )
max_p = max(max_p, prices[i])
max_profit = 0
for i in range(1,len(prices)-1):
# 注意可以同一天买卖股票
# 可以在 i 天,卖掉旧股票, 卖新股票
max_profit = max(max_profit, dp1[i]+dp2[i])
return max_profit
123. 买卖股票的最佳时机 III
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 思路概述 I、只许购买一次股票。遍历所有时间的股票价格，以当前股票价格之前出现过的最低价作为买入价，并计算出当天价...
- 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你可以尽...
