455 分發餅干
假設你是一位很棒的家長，想要給你的孩子們一些小餅干。但是，每個孩子最多只能給一塊餅干。
對每個孩子?i，都有一個胃口值?g[i]，這是能讓孩子們滿足胃口的餅干的最小尺寸；并且每塊餅干?j，都有一個尺寸?s[j]?。如果?s[j]?>= g[i]，我們可以將這個餅干?j?分配給孩子?i?，這個孩子會得到滿足。你的目標是滿足盡可能多的孩子，并輸出這個最大數值。
示例?1:
輸入: g = [1,2,3], s = [1,1] 輸出: 1
示例?2:
輸入: g = [1,2], s = [1,2,3] 輸出: 2小餅干先喂飽小胃口，貪心算法
int cmp(const void *a,const void *b){return *(int*)a-*(int*)b;
}
int findContentChildren(int* g, int gSize, int* s, int sSize) {int cnt=0;qsort(g,gSize,sizeof(int),cmp);qsort(s,sSize,sizeof(int),cmp);int j=0;for(int i=0;i<sSize;i++){if(s[i]>=g[j]){cnt++;j++;if(j==gSize)break;}}return cnt;
}376 擺動序列
如果連續數字之間的差嚴格地在正數和負數之間交替，則數字序列稱為?擺動序列 。第一個差（如果存在的話）可能是正數或負數。僅有一個元素或者含兩個不等元素的序列也視作擺動序列。
-
例如，?
[1, 7, 4, 9, 2, 5]?是一個?擺動序列?，因為差值?(6, -3, 5, -7, 3)?是正負交替出現的。 - 相反，
[1, 4, 7, 2, 5]?和?[1, 7, 4, 5, 5]?不是擺動序列，第一個序列是因為它的前兩個差值都是正數，第二個序列是因為它的最后一個差值為零。
子序列?可以通過從原始序列中刪除一些（也可以不刪除）元素來獲得，剩下的元素保持其原始順序。
給你一個整數數組?nums?，返回?nums?中作為?擺動序列?的?最長子序列的長度?。
示例 1：
輸入：nums = [1,7,4,9,2,5] 輸出：6 解釋：整個序列均為擺動序列，各元素之間的差值為 (6, -3, 5, -7, 3) 。
示例 2：
輸入：nums = [1,17,5,10,13,15,10,5,16,8] 輸出：7 解釋：這個序列包含幾個長度為 7 擺動序列。 其中一個是 [1, 17, 10, 13, 10, 16, 8] ，各元素之間的差值為 (16, -7, 3, -3, 6, -8) 。
示例 3：
輸入：nums = [1,2,3,4,5,6,7,8,9] 輸出：2
解題思路：
局部最優：刪除單調坡度上的節點（不包括單調坡度兩端的節點），那么這個坡度就可以有兩個局部峰值。
整體最優：整個序列有最多的局部峰值，從而達到最長擺動序列。
貪心算法，選擇最高點和最低點。pre和next分別是前一個差值和后一個差值。pre和next一正一負即可。pre跟著next走
考慮特殊情況
（1）首尾元素，至少滿足一個。設最后一個元素一定滿足，cnt初始值設為1，循環i小于numsSize-1。不算末尾
那怎么把滿足題意的首元素也加進去呢？
解決方法：設pre初始值為0，next>0或者<0都能滿足
（2）平坡情況，更特殊的是單調段出現平坡
比如 1 2 2 4， 如果pre每次都跟著next走，那最長子序列的長度應該為3，顯然是錯誤的。
所以我們只在坡度變化是才更新pre的值。
int wiggleMaxLength(int* nums, int numsSize) {//因為要算pre和next,pre初始值為0，表示第一個滿足題意//因為最后一個元素沒有next,所有cnt初始為1，int cnt=1;int pre=0,next;for(int i=0;i<numsSize-1;i++){next=nums[i+1]-nums[i];//1 2 2 3 4 單調有平坡情況if((next>0&&pre<=0)||(next<0&&pre>=0)){cnt++;pre=next;//坡度變化才更新pre的值}}return cnt;
}53 最大子數組和
給你一個整數數組?nums?，請你找出一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。
子數組是數組中的一個連續部分。
示例 1：
輸入：nums = [-2,1,-3,4,-1,2,1,-5,4] 輸出：6 解釋：連續子數組?[4,-1,2,1] 的和最大，為?6 。
示例 2：
輸入：nums = [1] 輸出：1
示例 3：
輸入：nums = [5,4,-1,7,8] 輸出：23
不要把max初始值設置為0，因為可能數組全是負數，不妨max初始值設為nums[0]
局部最優：當前連續和為負數的時候立刻放棄，從下一個元素重新計算連續和，因為負數加下一個元素 連續和只會越來越小。
全局最優：選取最大連續和
int maxSubArray(int* nums, int numsSize) {int max=nums[0],sum=0;//sum為區間和for(int i=0;i<numsSize;i++){sum+=nums[i];if(sum>=max)max=sum;if(sum<0)sum=0;//重置計算初始位置}return max;
}
