今日總結：

? ? ? ? 擺動序列的三種特殊情況需要著重思考，感覺是沒有思考清楚

基礎理論

? ? ? ? 1、貪心的本質：

? ? ? ? ? ? ? ? 貪心的本質是選擇每一階段的局部最優，從而達到全局最優。

? ? ? ? ? ? ? ? 例如：一堆鈔票，只能拿走10張，如何拿走最多的金額？：每次拿最大的（局部最優），最后就是拿走最多的金額（全局最優）

? ? ? ?2、 貪心的套路：

? ? ? ? ? ? ? ? 貪心算法沒有固定的套路。

? ? ? ? ? ? ? ? 難點：如何通過局部最優推理出全局最優（也沒有具體的套路）

? ? ? ? ? ? ? ? 如何驗證可不可以使用貪心算法：

? ? ? ? ? ? ? ? ? ? ? ? 舉反例，如果想不到反例就可以嘗試使用貪心算法

? ? ? ? 3、貪心的一般解題思路（雞肋，實際做題不能按照這個考慮）：

? ? ? ? ? ? ? ? （1）將問題分解為若干個子問題

? ? ? ? ? ? ? ? （2）找出適合的貪心策略

? ? ? ? ? ? ? ? （3）求解每一個子問題的最優解

? ? ? ? ? ? ? ? （4）將局部最優解堆疊成全局最優解

? ? ? ? ? ? ? ? 實際做題中，只需要考慮局部最優是什么，如何推導出全局最優

分發餅干

題目鏈接：455. 分發餅干 - 力扣（LeetCode）

總體思路：

? ? ? ? 將每一塊餅干都能夠給到適合的孩子，就能達到盡可能多的孩子。

? ? ? ? 所以，將餅干從小到大排序， 對孩子的胃口值也從小到大排序，盡量將每一塊小餅干都能分給對應的小孩子。

總體代碼：

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {//對兩者都進行排序sort(g.begin(),g.end());sort(s.begin(),s.end());//一個記錄分配的變量int sum=0;//遍歷餅干，從最小的胃口值開始分配for(int i=0,j=0;j<s.size();j++){if(i<g.size()&&s[j]>=g[i]){//滿足胃口值，滿足局部最合適，進行下一個孩子，同時記錄i++;sum++;}}return sum;}
};

擺動序列

題目鏈接：376. 擺動序列 - 力扣（LeetCode）

總體思路：

? ? ? ? 1、首先理解擺動序列的含義：連續數字之間的差嚴格的在正數和負數之間交替，則這個數字序列稱為擺動序列，少于兩個元素的序列也是擺動序列。

? ? ? ? 2、目標：

? ? ? ? ? ? ? ? （1）現在給定的序列是一個未知的序列：

? ? ? ? ? ? ? ? （2）需要通過刪除最少的元素去獲得最大的擺動序列，

? ? ? ? ? ? ? ? （3）且不能改變元素的原本位置。

? ? ? ? 3、方法：貪心算法：通過局部最優推導全局最優

? ? ? ? ? ? ? ? （1）局部最優：刪除單調坡度上的節點（頂、谷不刪除），那么這個坡度就有兩個局部峰值。

? ? ? ? ? ? ? ? （2）全局最優：整個序列擁有最多的局部峰值--->達到最長的擺動序列

? ? ? ? 4、尋找峰值情況的討論

? ? ? ? ? ? ? ? （1）上下坡中有平坡

? ? ? ? ? ? ? ? ? ? ? ? 需要刪除（不統計）平坡的前邊，只保留最后一個峰或者谷[i]-[i-1]<=0&&[i+1]-[i]>0或者[i]-[i-1]>=0&&[i+1]-[i]<0才記錄

? ? ? ? ? ? ? ? （2）數組首尾兩端的記錄方法

? ? ? ? ? ? ? ? ? ? ? ? 因為現在討論的是通過當前的點與上一個點、下一個點的差獲得當前是不是峰谷，所以對于數組首尾的特殊（首沒有前一個元素，尾沒有下一個元素），可以通過假設數組前還有一個與首相同的元素，即默認峰值是1開始計算。

? ? ? ? ? ? ? ? ? ? ? ? 相當于提前記錄一個左邊的端點，去記錄的第二個值是左端點與右端點的峰，沒有記錄右端點

? ? ? ? ? ? ? ? （3）單調坡中有平坡

? ? ? ? ? ? ? ? ? ? ? ? 在第（1）種中討論了上下坡中有平坡，處理方法是不去記錄前邊平的位置，但是在單調的坡中如果有平坡，可能會記錄上平坡的右邊位置，導致位置變多，所以需要在每次獲取到當前位置的左右坡度后，需要將左邊的坡度=右邊的坡度，在下次計算的時候就會處理掉單調坡有平坡的現象。

? ? ? ? ? ? ? ? ? ? ? ? 相當于只記錄峰值變化，只要沒有出現峰值，就不去記錄，也就是將前一個峰值的坡度記錄下來，只要當前坡度不相反，就不去記錄。

總體代碼：

class Solution {
public://核心尋找局部最優，即不記錄坡度中的值，只記錄峰值//需要注意三點：//（1）坡度有平坡的現象//（2）對于起始與結束的位置（因為要三個點比較）//（3）對于單調的坡中存在平坡現象int wiggleMaxLength(vector<int>& nums) {int length =1;//記錄長度，從1開始，因為除去起始位置的默認坡度int pre=0;int cur=0;//定義當前的坡度for(int i=0;i<nums.size()-1;i++)//因為默認左端點前有一個與左端點一樣的值，不去記錄右端點的位置了{   //使用cur去更新pre，從而避免單調坡中出現平坡的問題if(nums.size()<1)return length;//記錄當前的坡度cur = nums[i+1]-nums[i];if((pre<=0&&cur>0)||(pre>=0&&cur<0)){length++;//更新前一個坡度，只有在記錄峰值的時候才會更新坡度，不是每次計算cur都更新前一個的坡度pre = cur;}}return length;}
};

最大子序和

題目鏈接：53. 最大子數組和 - 力扣（LeetCode）

總體思路：

? ? ? ? 序列中存在正數、負數，求這個序列中的連續的子序列最大的和：所以要著重注意負數的影響，因為正數總是將和增大，負數會將和減小? 。

? ? ? ? 如果從某個值開始的子序列的和為負數了：說明當前值是一個負數，且與之前子序列的和加起來都要小于0，這個數只會影響整體的和，所以直接跳過當前的這個負數，從下一個值重新記錄子序列的和。

? ? ? ? 但是如果只是加上一個小的負數，整體結果仍舊大于0，不能重新開始記錄，因為后邊如果有大的正數，會使整體子序列的和變得更大。

? ? ? ? 所以，只有當前子序列的和為負數的時候，才從當前值的下一個值開始記錄子序列的和，也就是貪心思想，局部的最大，推導出全局的最大。

總體代碼：

class Solution {
public://最大和肯定和負值有關系，因為正值只會增加和//當目前的和小于0，就要舍棄，從新計算連續子序列的和（當前負數比之前所有的數之和都小，一定不能帶這個負數，不如后邊的自己相加）int maxSubArray(vector<int>& nums) {int sum = INT_MIN;//記錄最大的和int cur_sum = 0;//記錄當前的和for(int i=0;i<nums.size();i++){cur_sum += nums[i];//判斷當前的子序列的和是不是大于sumsum = sum >cur_sum?sum : cur_sum;if(cur_sum<0) cur_sum=0;}return sum;}
};