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