貪心有時候比動態規劃更巧妙，更好用！
通知：一些錄友基礎比較薄弱，不知道從哪里開始刷題。可以看一下公眾號左下角的「算法匯總」，「算法匯總」已經把題目順序編排好了，這是全網最詳細的刷題順序了，方便錄友們從頭打卡學習，「算法匯總」會持續更新！
題目鏈接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
給定一個數組，它的第 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。
提示：
本題首先要清楚兩點：
想獲得利潤至少要兩天為一個交易單元。
這道題目可能我們只會想，選一個低的買入，在選個高的賣，在選一個低的買入.....循環反復。
「如果想到其實最終利潤是可以分解的，那么本題就很容易了！」
如果分解呢？
假如第0天買入，第3天賣出，那么利潤為：prices[3] - prices[0]。
相當于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。
「此時就是把利潤分解為每天為單位的維度，而不是從0天到第3天整體去考慮！」
那么根據prices可以得到每天的利潤序列：(prices[i] - prices[i - 1]).....(prices[1] - prices[0])。
如圖：
122.買賣股票的最佳時機II
一些同學陷入：第一天怎么就沒有利潤呢，第一天到底算不算的困惑中。
第一天當然沒有利潤，至少要第二天才會有利潤，所以利潤的序列比股票序列少一天！
從圖中可以發現，其實我們需要收集每天的正利潤就可以，「收集正利潤的區間，就是股票買賣的區間，而我們只需要關注最終利潤，不需要記錄區間」。
那么只收集正利潤就是貪心所貪的地方！
「局部最優：收集每天的正利潤，全局最優：求得最大利潤」。
局部最優可以推出全局最優，找不出反例，試一試貪心！
對應C++代碼如下：
class Solution {public: int maxProfit(vector<int>& prices) { int result = 0; for (int i = 1; i < prices.size(); i++) { result += max(prices[i] - prices[i - 1], 0); } return result; }};動態規劃將在下一個系列詳細講解，本題解先給出我的C++代碼（帶詳細注釋），感興趣的同學可以自己先學習一下。
class Solution {public: int maxProfit(vector<int>& prices) { // dp[i][1]第i天持有的最多現金 // dp[i][0]第i天持有股票后的最多現金 int n = prices.size(); vector<vector<int>> dp(n, vector<int>(2, 0)); dp[0][0] -= prices[0]; // 持股票 for (int i = 1; i < n; i++) { // 第i天持股票所剩最多現金 = max(第i-1天持股票所剩現金, 第i-1天持現金-買第i天的股票) dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]); // 第i天持有最多現金 = max(第i-1天持有的最多現金，第i-1天持有股票的最多現金+第i天賣出股票) dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]); } return max(dp[n - 1][0], dp[n - 1][1]); }};股票問題其實是一個系列的，屬于動態規劃的范疇，因為目前在講解貪心系列，所以股票問題會在之后的動態規劃系列中詳細講解。
「可以看出有時候，貪心往往比動態規劃更巧妙，更好用，所以別小看了貪心算法」。
「本題中理解利潤拆分是關鍵點！」 不要整塊的去看，而是把整體利潤拆為每天的利潤。
一旦想到這里了，很自然就會想到貪心了，即：只收集每天的正利潤，最后穩穩的就是最大利潤了。
就醬，「代碼隨想錄」是技術公眾號里的一抹清流，值得推薦給你的朋友同學們！
打算從頭開始打卡的錄友，可以在「算法匯總」這里找到歷史文章，很多錄友都在從頭打卡，你并不孤單！
