121.买卖股票的最佳时机
题目描述
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
思路
暴力法
一次遍历
遍历一遍数组，计算每次 到当天为止 的最小股票价格和最大利润。
3. 动态规划
动态规划一般分为一维、二维、多维（使用状态压缩），对应形式为 dp(i)、dp(i)(j)、二进制dp(i)(j)。
（1）动态规划做题步骤
明确 dp(i) 应该表示什么（二维情况：dp(i)(j)）；
根据 dp(i)和 dp(i−1) 的关系得出状态转移方程；
确定初始条件，如 dp(0)。
（2）本题思路
其实方法一的思路不是凭空想象的，而是由动态规划的思想演变而来。这里介绍一维动态规划思想。
dp[i] 表示前 i 天的最大利润，因为我们始终要使利润最大化，则：
dp[i]=max(dp[i−1],prices[i]−minprice)
代码
class Solution(object):
def maxProfit(self, prices):
"""
暴力法(超出时间限制)
:type prices: List[int]
:rtype: int
"""
# ans = 0
#
# for i in range(0, len(prices)):
# for j in range(i + 1, len(prices)):
# ans = max(ans, prices[j] - prices[i])
#
# return ans
if len(prices) < 2:
return 0
result = max([prices[j] - prices[i] for i in range(0, len(prices)) for j in range(i + 1, len(prices))])
return result if result > 0 else 0
def maxProfit1(self, prices):
"""一次遍历"""
minprice = max(prices) # 记录最小的股值
maxprofit = 0 #
# 循环迭代输入的prices，当前价格小于最小的股值时修改minprice，
# 当前获得的利润大于最大的利润时修改maxprofit
for price in prices:
maxprofit = max(price - minprice, maxprofit)
minprice = min(price, minprice)
return maxprofit
def maxProfit2(self, prices):
"""动态规划（按照估值最低点列动态规划方程）"""
maxprofit = 0
dp = [prices[0] for j in range(0, len(prices))]
for i in range(1, len(prices)):
dp[i] = min(dp[i-1], prices[i])
maxprofit = max(maxprofit, prices[i] - dp[i])
return maxprofit
def maxProfit3(self, prices):
"""动态规划（按照最大利润列动态规划方程）"""
minprice = prices[0]
dp = [0]*len(prices)
for i in range(0, len(prices)):
minprice = min(minprice, prices[i])
dp[i] = max(dp[i - 1], prices[i] - minprice)
return dp[-1]
if __name__ == "__main__":
slt = Solution()
prices = [7, 1, 5, 3, 6, 4]
# prices = [7, 6, 4, 3, 1]
# profit = slt.maxProfit(prices)
# profit = slt.maxProfit1(prices)
# profit = slt.maxProfit2(prices)
profit = slt.maxProfit3(prices)
print(profit)