題目描述：

給定一個(gè)數(shù)組，它的第?i 個(gè)元素是一支給定股票第 i 天的價(jià)格。

設(shè)計(jì)一個(gè)算法來(lái)計(jì)算你所能獲取的最大利潤(rùn)。你可以盡可能地完成更多的交易（多次買賣一支股票）。

注意：你不能同時(shí)參與多筆交易（你必須在再次購(gòu)買前出售掉之前的股票）。

示例 1:

輸入: [7,1,5,3,6,4]

輸出: 7

解釋: 在第 2 天（股票價(jià)格 = 1）的時(shí)候買入，在第 3 天（股票價(jià)格 = 5）的時(shí)候賣出, 這筆交易所能獲得利潤(rùn) = 5-1 = 4 。

?? ? 隨后，在第 4 天（股票價(jià)格 = 3）的時(shí)候買入，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣出, 這筆交易所能獲得利潤(rùn) = 6-3 = 3 。

示例 2:

輸入: [1,2,3,4,5]

輸出: 4

解釋: 在第 1 天（股票價(jià)格 = 1）的時(shí)候買入，在第 5 天 （股票價(jià)格 = 5）的時(shí)候賣出, 這筆交易所能獲得利潤(rùn) = 5-1 = 4 。

?? ? 注意你不能在第 1 天和第 2 天接連購(gòu)買股票，之后再將它們賣出。

?? ? 因?yàn)檫@樣屬于同時(shí)參與了多筆交易，你必須在再次購(gòu)買前出售掉之前的股票。

示例?3:

輸入: [7,6,4,3,1]

輸出: 0

解釋: 在這種情況下, 沒(méi)有交易完成, 所以最大利潤(rùn)為 0。

解法：

1.貪心

比較每個(gè)前后兩天的差值 如果大于0 則加到利潤(rùn)里 代表前一天買 當(dāng)天賣 大于0代表就有利潤(rùn) 把所有有利潤(rùn)的情況相加 就是最大利潤(rùn)

2.動(dòng)態(tài)規(guī)劃

第n天如果沒(méi)有持有股票 等于上一天沒(méi)有持有股票 和上一天持有這一天賣掉的較大值

第n天如果持有股票 等于上一天持有股票 和上一天沒(méi)有這一天買入的較大值

最后返回dp[len-1][0]