代码随想录第二十七天（一刷C语言）|分发饼干摆动序列最大子数组和

创作目的：为了方便自己后续复习重点，以及养成写博客的习惯。

一、分发饼干

思路：参考carl文档

局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩。尝试使用贪心策略，先将饼干数组和小孩数组排序。再从后向前遍历小孩数组，用大饼干优先满足胃口大的，并统计满足小孩数量。

ledcode题目：https://leetcode.cn/problems/assign-cookies/description/

AC代码：

//小餅乾先餵飽小胃口的
int cmp(int* a, int* b) {
    return *a - *b;
}

int findContentChildren(int* g, int gSize, int* s, int sSize){
    if(sSize == 0)
        return 0;

    //将两个数组排序为升序
    qsort(g, gSize, sizeof(int), cmp);
    qsort(s, sSize, sizeof(int), cmp);

    int numFedChildren = 0;
    int i = 0;
    for(i = 0; i < sSize; ++i) {
        if(numFedChildren < gSize && g[numFedChildren] <= s[i])
            numFedChildren++;
    }
    return numFedChildren;
}

二、摆动序列

思路：参考carl文档

局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。贪心所贪的地方是让峰值尽可能的保持峰值

注意：上下坡中有平坡、数组首尾两端、单调坡中有平坡

lecode题目：https://leetcode.cn/problems/wiggle-subsequence/

AC代码：

int wiggleMaxLength(int* nums, int numsSize){
    if(numsSize <= 1)
        return numsSize;

    int length = 1;
    int preDiff , curDiff;
    preDiff = curDiff = 0;
    for(int i = 0; i < numsSize - 1; ++i) {
        // 计算当前i元素与i+1元素差值
        curDiff = nums[i+1] - nums[i];

        // 若preDiff与curDiff符号不符，则子序列长度+1。更新preDiff的符号
        // 若preDiff与curDiff符号一致，当前i元素为连续升序/连续降序子序列的中间元素。不被记录入长度
        // 注：当preDiff为0时，curDiff为正或为负都属于符号不同
        if((curDiff > 0 && preDiff <= 0) || (preDiff >= 0 && curDiff < 0)) {
            preDiff = curDiff;
            length++;
        }
    }

    return length;
}

三、最大子数组和

思路：参考carl文档

局部最优：当前连续和为负数时舍弃，从下一个元素重新计算连续和，负数会使连续和变小。全局最优：选取最大连续和。遍历 nums，从头开始用 count 累积，如果 count 一旦加上 nums[i]变为负数，那么就从 nums[i+1]开始从 0 累积 count 了。既不断调整最大子序和区间的起始位置。区间的终止位置，其实就是 count 取到最大值。

ledcode题目：https://leetcode.cn/problems/maximum-subarray/description/

AC代码：

int maxSubArray(int* nums, int numsSize){
    int maxVal = INT_MIN;
    int subArrSum = 0;

    int i;
    for(i = 0; i < numsSize; ++i) {
        subArrSum += nums[i];
        // 若当前局部和大于之前的最大结果，对结果进行更新
        maxVal = subArrSum > maxVal ? subArrSum : maxVal;
        // 若当前局部和为负，对结果无益。则从nums[i+1]开始应重新计算。
        subArrSum = subArrSum < 0 ? 0 : subArrSum;
    }

    return maxVal;
}