给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出,
这笔交易所能获得利润 = 5-1 = 4 。随后，在第 4 天（股票价格 = 3）的时候买入，
在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出,
这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票，
之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
1 <= prices.length <= 3 * 10 ^ 4
0 <= prices[i] <= 10 ^ 4
自我解答(贪心解法)
很容易确认什么时候买入和卖出
买入：下一天的价格大于当天的价格
卖出：下一天的价格小于当天的价格
class Solution:
def maxProfit(self, prices: List[int]) -> int:
length = len(prices)
if length < 2:
return 0
buy_price = -1
profit = 0
for i in range(0, length-1):
if buy_price >= 0:
if prices[i] > prices[i+1]:
profit += prices[i] - buy_price
buy_price = -1
elif prices[i] < prices[i+1]:
buy_price = prices[i]
if buy_price >= 0 and prices[i+1] > buy_price:
profit += prices[i+1] - buy_price
return profit
动态规划题解
我没有想出解决方案，看了题解后发现，我似乎不可能会想到那么来做。
需要注意题意：多次买卖一支股票。因此不存在用赚来的钱买多支股票的情况
和前面遇到动态规划问题不太一样的是，题解把原问题转化成了 两个最优问题：
f0(i): 第 i 天 没有持仓的 最大现金值
f1(i): 第 i 天 有持仓的 剩余最大现金值
所以，如果 prices数组长度为 n, 那么最大利润就是 f0(n-1)
最优子结构：
f0(i) = max(f0(i-1), f1(i-1) + prices[i])
解释：
可能是不操作，等于 前一天的 无持仓最大现金值
也可能是有卖出操作，即 等于 前一天有持仓的剩余最大现金值 + 当天的股价
f1(i) = max(f1(i-1), f0(i-1) - prices(i))
解释：
可能是不操作，等于 前一天的 有持仓的剩余最大现金值
也可能是有买入操作， 即 等于 前一天无持仓的最大现金值 - 当天的股价
自顶向下，会发现最小子问题：
f0(0) = 0 # 解释：没有持仓的话，也就是是一开始不买不卖，因此现金值为 0
f1(0) = -prices(0) # 解释：第一天要有持仓，则说明以当天股价买进了，现金值为 -prices[0]
就是这样，分解两个最优问题，两者的子问题互相配合，以此得到原问题的最优解
自底向上的动态规划算法
class Solution3:
def maxProfit(self, prices: List[int]) -> int:
dp0, dp1 = 0, -prices[0]
for price in prices[1:]:
dp0, dp1 = max(dp0, dp1 + price), max(dp1, dp0 - price)
return dp0
总结
研究题解思路后发现，凭借自己当前的能力，是很难想出动态规划解法的。
我最多能想到题解转化的第一个最优问题。然而，转化成第二个最优问题，然后两者互相配合的做法，
我似乎想破脑袋也不会想到。因为在前面的碰到的动态规划问题中，基本都只是把从原最优问题分解入手，
而且《算法导论》中也没介绍这种 转化成一个或多个最优问题的求解方式，更别说让这些转化问题互相配合呢。
这就好像是一门“内功心法”，基本理论只是皮毛，会变换运用，才算是进阶了。
看来只能多练习了，去体会众多 "招式"的变换，以此逐渐习得 “动态规划”
原题链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii