主要思路：因為只有一股可以交易，所以我們可以枚舉 必須以i位置作為賣出時機的情況下，得到的最大收益是多少。如果我們得到每個i位置的最大收益，那麼最大收益必是所有位置的最大收益的最大值 。
使用兩個變數：
min變數：表示遍歷到的位置之前的最小值是什麼。
max變數：表示當前收集到必須以i位置賣出的最大收益是多少。
遍歷數組一遍，在遍歷到i位置的時候，min和max的更新邏輯如下：
遍歷完數組，返回max的值就是最終答案。完整代碼見：
主要思路：由於可以進行任意次的交易，但是任何時候最多隻能持有一股股票，所以我們可以把股票曲線的所有 上升段 都抓取到，累加收益就是最大收益。遍歷數組，遍歷到的位置減去前一個位置的值，如果是正數，就收集，如果是負數，就把本次收益置為0（就等於沒有做這次交易），這樣遍歷一遍數組，就不會錯過所有的收益。
設置一個變數max，初始為0，用於收集最大收益值，來到i位置，max更新邏輯如下：
完整代碼如下：
由本題可以簡單得出一個結論： 如果數組元素個數為N，則最多執行N/2次交易就可以抓取所有的上升段的值（極端情況下，當前時刻買，下一個時刻賣，保持這樣的交易一直到最後，執行的交易次數就是N/2） 。
主要思路：
在第2種情況下，我們定義
其中dp[i][j]表示[0...i]范圍內交易j次獲得的最大收益是多少。如果可以把dp這個二維表填好，那麼返回dp[N-1][k]的值就是題目要的答案。
dp這個二維矩陣中，
第一行的值表示數組[0..0]范圍內，交易若干次的最大收益，顯然，都是0。
第一列的值表示數組[0...i]范圍內，交易0次獲得的最大收益，顯然，也都是0。
針對任何一個普遍位置dp[i][j]的值，
我們可以枚舉i位置是否參與交易，如果i位置不參與交易，那麼dp[i][j] = dp[i-1][j]，如果i位置參與交易，那麼i位置一定是最後一次的賣出時機。
那最後一次買入的時機，可以是如下情況：
最後一次買入的時機在i位置，那麼dp[i][j] = dp[i][j-1] - arr[i] + arr[i]
最後一次買入的時機在i-1位置，那麼dp[i][j] = dp[i-1][j-1] - arr[i-1] + arr[i]
最後一次買入的時機在i-2位置，那麼dp[i][j] = dp[i-2][j-1] - arr[i-2] + arr[i]
...
最後一次買入的時機在0位置，那麼dp[i][j] = dp[0][j-1] - arr[0] + arr[i]
完整代碼如下：
上述代碼中包含一個枚舉行為
增加了時間復雜度，我們可以優化這個枚舉。
我們可以舉一個具體的例子來說明如何優化，
比如，
當我們求dp[5][3]這個值，我們可以枚舉5位置是否參與交易，假設5位置不參與交易，那麼dp[5][3] = dp[4][3]，假設5位置參與交易，那麼5位置一定是最後一次的賣出時機。那最後一次買入的時機，可以是如下情況：
最後一次買入的時機在5位置，那麼dp[5][3] = dp[5][2] - arr[5] + arr[5]
最後一次買入的時機在4位置，那麼dp[5][3] = dp[4][2] - arr[4] + arr[5]
最後一次買入的時機在3位置，那麼dp[5][3] = dp[3][2] - arr[3] + arr[5]
最後一次買入的時機在2位置，那麼dp[5][3] = dp[2][2] - arr[2] + arr[5]
最後一次買入的時機在1位置，那麼dp[5][3] = dp[1][2] - arr[1] + arr[5]
最後一次買入的時機在0位置，那麼dp[5][3] = dp[0][2] - arr[0] + arr[5]
我們求dp[4][3]這個值，我們可以枚舉4位置是否參與交易，假設4位置不參與交易，那麼dp[4][3] = dp[3][3]，假設4位置參與交易，那麼4位置一定是最後一次的賣出時機。那最後一次買入的時機，可以是如下情況：
最後一次買入的時機在4位置，那麼dp[4][3] = dp[4][2] - arr[4] + arr[4]
最後一次買入的時機在3位置，那麼dp[4][3] = dp[3][2] - arr[3] + arr[4]
最後一次買入的時機在2位置，那麼dp[4][3] = dp[2][2] - arr[2] + arr[4]
最後一次買入的時機在1位置，那麼dp[4][3] = dp[1][2] - arr[1] + arr[4]
最後一次買入的時機在0位置，那麼dp[4][3] = dp[0][2] - arr[0] + arr[4]
比較dp[5][3]和dp[4][3]的依賴關系，可以得到如下結論：
假設在求dp[4][3]的過程中，以下遞推式的最大值我們可以得到
dp[4][2] - arr[4]
dp[3][2] - arr[3]
dp[2][2] - arr[2]
dp[1][2] - arr[1]
dp[0][2] - arr[0]
我們把以上式子的最大值定義為best，那麼
dp[5][3] = Math.max(dp[4][3],Math.max(dp[5][2] - arr[5] + arr[5], best + arr[5]))
所以dp[5][3]可以由dp[4][3]加速得到，
同理，
dp[4][3]可以通過dp[3][3]加速得到，
dp[3][3]可以通過dp[2][3]加速得到，
dp[2][3]可以通過dp[1][3]加速得到，
dp[1][3]可以很簡單得出，dp[1][3]有如下幾種可能性:
可能性1，1位置完全不參與，則
可能性2，1位置作為最後一次的賣出時機，買入時機是1位置
可能性3，1位置作為最後一次的賣出時機，買入時機是0位置
此時，best的值為
然後通過dp[1][3]加速dp[2][3]，通過dp[2][3]加速dp[3][3]......，所以二維dp的填寫方式是按列填，
先填dp[1][0]，dp[1][2]一直到dp[1][k]，填好第一列；
然後填dp[2][0],dp[2][1]一直到dp[2][k]，填好第二列；
...
依次填好每一列，直到填完第N-1列。
枚舉行為被優化，優化枚舉後的完整代碼如下：
主要思路：上一個問題中，令k=2就是本題的答案。
主要思路：因為有了冷凍期，所以每個位置的狀態有如下三種：
定義三個數組，分別表示i位置這三種情況下的最大值是多少
顯然有如下結論：
針對一個普遍位置i
最大收益就是如上三種方式的最大值。完整代碼見：
由於三個數組有遞推關系，所以可以用三個變數替換三個數組，做空間壓縮，優化後的代碼如下：
主要思路：由於沒有冷凍期，所以在i位置的時候，狀態只有兩種
針對0位置
針對普遍位置i
完整代碼如下：
同樣的，兩個數組都有遞推關系，可以做空間壓縮，簡化後的代碼如下：
原文鏈接：買賣股票的最佳時機系列問題 - Grey Zeng - 博客園