买卖股票的最佳时间 I
题目
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
示例:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
// time:O(n) space:O(1)
class Solution:
def maxProfit(self,prices):
n=len(prices)
if n==0:return 0
dp=[0]*n
minprice=prices[0]
for i in range(n):
minprice=min(minprice,prices[i])
dp[i]=max(prices[i]-minprice,dp[i-1])
return dp[-1]
买卖股票最佳时机 II
题目
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
示例：
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第2天（股票价格 = 1）的时候买入，在第3天（股票价格=5）的时候卖出, 这笔交易所能获得利润=5-1=4 。
随后，在第4天（股票价格=3）的时候买入，在第5天（股票价格=6）的时候卖出, 这笔交易所能获得利润=6-3=3 。
方法一（贪心算法）
算法流程
- 遍历整个股票交易日价格列表 price，策略是所有上涨交易日都买卖（赚到所有利润），所有下降交易日都不买卖（永不亏钱）。
- 设 tmp 为第 i-1 日买入与第 i 日卖出赚取的利润，即 tmp = prices[i] - prices[i - 1] ；
- 当该天利润为正 tmp > 0，则将利润加入总利润 profit；当利润为 00 或为负，则直接跳过；
- 遍历完成后，返回总利润 profit。
// time:O(n) space:O(1)
class Solution:
def maxProfit(self,prices):
n=len(prices)
profit=0
for i in range(1,n):
temp=prices[i]-prices[i-1]
if temp>0:
profit+=temp
return profit
方法二（动态规划）
第一步：定义状态
状态dp[i][j]定义如下：
- 第一维 i 表示索引为 i 的那一天（具有前缀性质，即考虑了之前天数的收益）能获得的最大利润；
- 第二维 j 表示索引为 i 的那一天是持有股票，还是持有现金。这里 0 表示持有现金（cash），1 表示持有股票（stock）。
第二步：思考状态转移方程
- 状态从持有现金（cash）开始，到最后一天我们关心的状态依然是持有现金（cash）；
- 每一天状态可以转移，也可以不动。状态转移用下图表示：
说明：
- 因为不限制交易次数，除了最后一天，每一天的状态可能不变化，也可能转移；
- 写代码的时候，可以不用对最后一天单独处理，输出最后一天，状态为 0 的时候的值即可。
第3步：确定起始
起始的时候：
- 如果什么都不做，dp[0][0] = 0；
- 如果买入股票，当前收益是负数，即 dp[0][1] = -prices[i]；
第4步：确定终止
终止的时候，上面也分析了，输出 dp[len - 1][0]，因为一定有 dp[len - 1][0] > dp[len - 1][1]。
// time:O(n) space:O(n)
class Solution:
def maxProfit(self, prices):
n=len(prices)
if n<2:return 0
dp=[[0]*2 for _ in range(n)]
dp[0][0]=0
dp[0][1]=-prices[0]
for i in range(1,n):
dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])
dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i])
return dp[n-1][0]
// 改进版，复杂度同上
class Solution:
def maxProfit(self, prices):
n=len(prices)
if n<2:return 0
//hold:持有股票
//cash:持有现金
//状态转移:cash->hold->cash->hold->cash->hold->cash
cash,hold=0,-princes[0]
preCash,preHold=cash,hold
for i in range(n):
cash=max(preCash,preHold+princes[i])
hold=max(preHold,preCash-princes[i])
preCash=cash
preHold=hold
return cash