Day 31 贪心01
理论基础
贪心的本质是选择每一阶段的局部最优，从而达到全局最优。最好用的策略就是举反例，如果想不到反例，那么就试一试贪心吧。
贪心算法一般分为如下四步：
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
455.分发饼干
题目链接：455. 分发饼干 - 力扣（LeetCode）
class Solution {public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int count = 0;int start = 0;for(int i = 0; i < s.length && start < g.length; i++){if(s[i] >= g[start]) {start++;count++;}}return count;}
}376. 摆动序列
题目链接：376. 摆动序列 - 力扣（LeetCode）
思路：当前差值和上一个差值进行比较
class Solution {public int wiggleMaxLength(int[] nums) {if(nums.length <= 1){return nums.length;}int curdiff = 0;int prediff = 0;int count = 1;for(int i = 1; i < nums.length; i++){curdiff = nums[i] - nums[i-1];if((curdiff > 0 && prediff <= 0) || (curdiff < 0 && prediff >=0) ){count++;prediff = curdiff;}}return count;}
}53. 最大子序和
题目链接：53. 最大子数组和 - 力扣（LeetCode）
思路：
class Solution {public int maxSubArray(int[] nums) {if(nums.length == 1){return nums[0];}int maxsum = nums[0];int sum =0;for(int i = 0; i < nums.length; i++){sum += nums[i];maxsum = Math.max(maxsum,sum);if(sum < 0) sum = 0;}return maxsum;}
}