代码随想录算法训练营第31天| 理论基础 |455.分发饼干 | 376. 摆动序列 |53. 最大子序和

代码随想录算法训练营第31天| 理论基础 |455.分发饼干 | 376. 摆动序列 |53. 最大子序和

第八章 贪心算法 part01

贪心算法其实就是没有什么规律可言，所以大家了解贪心算法 就了解它没有规律的本质就够了。

不用花心思去研究其规律， 没有思路就立刻看题解。

基本贪心的题目 有两个极端，要不就是特简单，要不就是死活想不出来。

学完贪心之后再去看动态规划，就会了解贪心和动规的区别。

详细布置

理论基础

https://programmercarl.com/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

455.分发饼干

https://programmercarl.com/0455.%E5%88%86%E5%8F%91%E9%A5%BC%E5%B9%B2.html

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(),g.end());//先都排序保证数组的有序
        sort(s.begin(),s.end());
        int result=0;
        int index=s.size()-1;//从后来满足最大容量的匹配
        

        for(int i=g.size()-1;i>=0;i--)
        {
                if(index>=0&&s[index]>=g[i])//保证匹配eg:s.size()=0
                {
                    result++;
                    index--;
                }
//其中i是固定的，从后最大胃口来匹配最大饼干，若最大饼干不匹配当前胃口，就是胃口的问题
//好理解就是最近比较有名的话，你不做有的是人做。你吃不饱（所以就不吃了（咋就闹上脾气了？（（恼）），有的是人吃的饱。
                
        }
        return result;

    }
};

376. 摆动序列

https://programmercarl.com/0376.%E6%91%86%E5%8A%A8%E5%BA%8F%E5%88%97.html

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if(nums.size()<=1)return nums.size();
        int curdiff=0;// 当前一对差值
        int prediff=0;// 前一对差值
        int result=1; // 记录峰值个数，序列默认序列最右边有一个峰值
        for(int i=0;i<nums.size()-1;i++)
        {
            curdiff=nums[i+1]-nums[i];
                        // 出现峰值

            if((prediff<=0&&curdiff>0)||(prediff>=0&&curdiff<0))
            {
                result++;
                prediff=curdiff;// 注意这里，只在摆动变化的时候更新prediff
            }


        }
        return result;
    }
};

53. 最大子序和

https://programmercarl.com/0053.%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C.html

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int result=INT32_MIN;
        int count=0;


        for(int i=0;i<nums.size();i++)
        {
            count+=nums[i];
            if(count>result)result=count;// 取区间累计的最大值（相当于不断确定最大子序终止位置）
            if(count<0) count=0;// 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
            
        }

    return result;}
};