贪心算法
题目的核心是让我们做不亏本的买卖。所以我们只需买所有的上涨交易日即可，下跌的都不买。利润profit记录数值，tmp来判断是亏损还是盈利。tmp = [i] - [i-1],将利润累加到profit中
代码
class Solution:
def maxProfit(self, prices: List[int]) -> int:
profit = 0
for i in range(1, len(prices)):
tmp = prices[i] - prices[i-1]
if tmp > 0: profit += tmp
return profit
动态规划
解题思路
因为此题会有多次交易的情况，我们并不清楚什么时候买入什么时候卖出，所以在设计算法的时候需要把这两种情况都考虑到。我们设:
- 利润
dp - 当天未持股的最大利润
dp[i][0] - 当天持股的最大利润
dp[i][1]
状态转移方程
如果当前交易日未持股，那么转移状态为：
- 前一天没有持有股票
- 前一天持有股票过，但是卖了并获得了
prices[i]的收益
当天未持有股票情况下的状态转移方程为：
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
同理如果当天持有股票，那么转移状态为：
- 前一天已经持有股票，即
dp[i-1][1] - 前一天未持有股票，但是买入了，即
dp[i-1][0] - prices[i]
当天持有股票情况下的状态转移方程为：
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
边界（初始状态）
第0天交易的情况肯定是:
- 未持有：
dp[0][0] = 0 - 持有：
dp[0][1] = -prices[0]
按照这个顺序从前往后计算便可计算出最终结果。由于可能存在两种情况，因为未持有股票的利润肯定是高于持有股票的利润，现金持有说了算嘛，所以最后返回的肯定是dp[n-1][0]
代码
class Solution:
def maxProfit(self, prices: List[int]) -> int:
N = len(prices)
if N < 2: return 0
dp = [[0]*2] * 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: List[int]) -> int:
N = len(prices)
if N < 2: return 0
dp0 = 0
dp1 = -prices[0]
for i in range(1, N):
newdp0 = max(dp0, dp1 + prices[i])
newdp1 = max(dp1, dp0 - prices[i])
dp0 = newdp0
dp1 = newdp1
return dp0
复杂度分析
时间复杂度：O(N)
空间复杂度：O(1)