贪心算法一般分为如下四步：
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
分发饼干
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(),g.end());
sort(s.begin(),s.end());
int index=s.size()-1;
int result=0;
for(int i=g.size()-1;i>=0;i--){
if(index>=0&&s[index]>=g[i]){
result++;
index--;
}
}
return result;
}
};
摆动序列
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
if(nums.size()==0) return 0;
if(nums.size()==1) return 1;
int prediff=0;
int curdiff=0;
int cnt=1;
for(int i=1;i<nums.size();i++){
curdiff=nums[i]-nums[i-1];
if((prediff>=0&&curdiff<0)||(prediff<=0&&curdiff>0)){
cnt++;
prediff = curdiff;
//cout<<curdiff<<endl;
}
}
return cnt;
}
};
最大子序和
如果 -2 1 在一起，计算起点的时候，一定是从1开始计算，因为负数只会拉低总和，这就是贪心贪的地方！
局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。
全局最优：选取最大“连续和”
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<0){
count=0;
}
result=max(result,count);
}
return result;
}
};
买卖股票的最佳时机II
局部最优：收集每天的正利润，全局最优：求得最大利润。
class Solution {
public:
int maxProfit(vector<int>& prices) {
int result = 0;
for (int i = 1; i < prices.size(); i++) {
result += max(prices[i] - prices[i - 1], 0);
}
return result;
}
};
