image.png
解题思路1 (动态规划)：
- 第i天没持有股票最大收益由两个状态转移来: 保持i-1天的状态，继续不持有，或者i-1天持有，第i天卖出； dp_0[i] = max(dp_0[i], dp_1[i-1]+prices[i])
- 第i天持有股票最大收益有两个状态转移来：保持i-1天的状态，持有股票，或者i-1没持有，第i天买入； dp_1[i] = max(dp_1[i-1], dp_0[i]-prices[i])
python3代码如下：
class Solution:
def maxProfit(self, prices: List[int]) -> int:
len1 = len(prices)
dp_0 = [0 for _ in range(len1)]
dp_1 = [0 for _ in range(len1)]
dp_1[0] = -prices[0]
for i in range(1, len(prices)):
dp_0[i] = max(dp_0[i-1], dp_1[i-1]+prices[i])
dp_1[i] = max(dp_1[i-1], dp_0[i-1]-prices[i])
return dp_0[-1]
解题思路2：
- 收益累加，假如比前一天数值大，则累加入总收益
python3代码如下：
class Solution:
def maxProfit(self, prices: List[int]) -> int:
maxProfit = 0
for i in range(1, len(prices)):
if prices[i] > prices[i-1]:
maxProfit += prices[i] - prices[i-1]
return maxProfit
解题思路3：
- 在思路1基础上的优化，取代了数组存储状态，只保留当天收益
python3代码如下：
class Solution:
def maxProfit(self, prices: List[int]) -> int:
len1 = len(prices)
dp_0 = 0
dp_1 = -prices[0]
for i in range(1, len(prices)):
dp_0 = max(dp_0, dp_1+prices[i])
dp_1 = max(dp_1, dp_0-prices[i])
return dp_0
