23贪心算法

分发饼干

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {int i=0,j=0;int count=0;sort(s.begin(),s.end());sort(g.begin(),g.end());while(i<g.size()&&j<s.size()){if(g[i]<=s[j]){i++;j++;count++;}else{j++;}}return count;}
};

摆动序列

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {int count=1;int prev=nums[0];bool neg=0;int start=1;for(int i=1;i<nums.size();i++){if(i==start){if(prev==nums[i]){start++;continue;}else{neg=nums[i]>prev?1:0;prev=nums[i];count++;continue;}}if(neg){if(nums[i]<prev){neg=0;prev=nums[i];count++;}else{prev=nums[i];}}else{if(nums[i]>prev){neg=1;prev=nums[i];count++;}else{prev=nums[i];}}}return count;}
};

最大子序列和

class Solution {
public:int maxSubArray(vector<int>& nums) {int res=-__INT32_MAX__;int max=res;for(int num:nums){if(res<0)res=num;else{res+=num;}if(res>max)max=res;}return max;}
};