贪心算法 part01

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;}
};

455.分发饼干

sort(begin(),end())

然后匹配就行；（但是代码随想录想的是用大的满足，颠倒一下饼干和投喂小孩遍历顺序就行）

376. 摆动序列

我理解了，就算是递增序列也算2！！（题目理解存在问题！！）

class Solution { 
public:int wiggleMaxLength(vector<int>& nums) {if(nums.size() < 2) return nums.size(); // 处理边界情况int count = 0;  // 初始化int flag = 0;   // 初始状态for(int i = 1; i < nums.size(); i++) {int a = nums[i] - nums[i-1]; // 计算当前差值if(a > 0 && flag <= 0) {     // 形成上升摆动count++;flag = 1;               // 更新状态为上升} else if(a < 0 && flag >= 0) { // 形成下降摆动count++;flag = -1;              // 更新状态为下降}// 当 a == 0 时，跳过，保持 flag 不变}return count+1; //我之前是 态势的比较，而元素需要+1； }
};

代码随想录

53. 最大子序和

我这里相当于自动获取了最大数值；

class Solution {
public:int maxSubArray(vector<int>& nums) {int mmax = INT_MIN;int last=0;int sum=0;int flag=0;if(nums.size()==0) return 0;if(nums.size()==1) return nums[0];for(int i=0; i<nums.size();i++){if(nums[i]>mmax) mmax=nums[i]; //全局最大单数last = max(sum,last); sum+=nums[i];last = max(sum,last); //是否更新最大数值if(sum<=0) {flag=1; sum=0;}}if(flag==1&&last<=0) return mmax;else return max(mmax,last);}
};

class Solution {
public:int maxSubArray(vector<int>& nums) {int mmax = nums[0]; // 记录全局最大值int sum = 0;        // 记录当前子数组的和for (int i = 0; i < nums.size(); i++) {sum += nums[i];           // 累加当前元素mmax = max(mmax, sum);    // 更新全局最大值---自动获取了最大数值if (sum < 0) sum = 0;     // 当前和为负时，重置为 0}return mmax; // 返回最大子数组和}
};