一、贪心算法
贪心算法核心思想是局部最优，以确定全局最优。当然需要使用数学归纳去总结，但是实际应用过程，可以举反例来验证是不是可以使用贪心算法。参考代码随想录
贪心算法一般分为如下四步：
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
二、分发饼干
根据贪心算法思想，题目中明确指出g[i]代表孩子的最大胃口，s[i]代表饼干的尺寸，可以思考，最大的饼干分给最大胃口的孩子，胃口小的孩子用小尺寸的饼干，这样整体上，能满足最多的孩子。
//贪心算法：局部最优，进而全局最优
void sort(int* arr, int size)
{
for(int i = 0; i < size; i++)
{
for(int j = i + 1; j < size; j++)
{
if(arr[i] > arr[j])
{
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
}
}
int findContentChildren(int* g, int gSize, int* s, int sSize) {
/**排序**/
sort(g, gSize);
sort(s, sSize);
int result = 0;
int s_idx = sSize - 1;
//最大的饼干s[i], 给胃口最大的孩子g[j]
for(int i = gSize - 1; i >= 0; i--)
{
//g[i]的第一个是孩子的最大的胃口, s[s_idx]是最大尺寸的饼干
if(s_idx >= 0 && g[i] <= s[s_idx])
{
result++;
s_idx--;
}
}
return result;
}还有一个思路：就是先给最小的胃口的孩子分最小尺寸的饼干，然后遍历，找到最多孩子数量。
三、摆动序列
贪心算法思路：摆动意味着左右有波动，可以考虑峰值点个数，就能判断全局最长的序列。
代码随想录上面的记录比较重要的点：1 要注意平峰时候的情况，比如单调区间，突然一段有平峰；还有类似梯形，开始有峰，然后平峰，接着递减；2 注意只有2个的情况，比如[0 0]这样的就只有一个长度序列；
int wiggleMaxLength(int* nums, int numsSize){
if(numsSize <= 1)//numssize = 2情况，例如[0, 0]在这里不行
{
return numsSize;
}
int pre = 0, cur = 0;
int result = 1;
for(int i = 1; i < numsSize; i++)
{
cur = nums[i] - nums[i -1];
if((pre <=0 && cur > 0) || (pre >=0 && cur < 0))
{
result++;
pre = cur;
}
}
return result;
}
四、最大子数组和
思路：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小 （负数加任何数都会越来越小）。
int maxSubArray(int* nums, int numsSize) {
int result = INT_MIN;
int sum = 0;
if(numsSize == 0)
{
return 0;
}
for(int i = 0; i < numsSize; i++)
{
sum += nums[i];
if(sum > result)
{
result = sum;
}
if(sum <= 0)
sum = 0;
}
return result;
}