代码随想录day23：贪心part1

455. 分发饼干 

class Solution {public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int res = 0;int index = s.length - 1;for(int i = g.length - 1; i >= 0; i--){if(index >= 0 && s[index] >= g[i]){res++;index--;}}return res;}
}

贪心的题没啥公式化的套路，在数学上找规律多做多练

376. 摆动序列

class Solution {public int wiggleMaxLength(int[] nums) {if(nums.length < 2) return nums.length;int pre = 0;int cur = 0;int res = 1;for(int i = 1; i < nums.length; i++){cur = nums[i] - nums[i - 1];if((cur > 0 && pre <= 0) || (cur < 0 && pre >=0)){res++;pre = cur;}}return res;}
}

三个数一个窗口滑动，一个大一个小为拐，需要注意1.平的时候只加一个，2.头的pre模拟为0，所以头都自动加一，3.尾的自动加体现在res = 1。所以细节也不少

import java.util.List;class Solution {public int wiggleMaxLength(int[] nums) {if (nums.length < 2) return nums.length;int result = 1;boolean up = true;boolean down = true;for (int i = 1; i < nums.length; i++) {if (up && nums[i] > nums[i - 1]) {  // 上升up = false;down = true;result++;} else if (down && nums[i] < nums[i - 1]) { // 下降down = false;up = true;result++;}}return result;}
}

hardcore-sinoussisfm - 力扣（LeetCode）的题解也很漂亮，我写了Java版本的。

思路为只需要统计上升和下降的次数即可！ 上升->下降-> 上升 。。。。。

53. 最大子数组和

本题三个思路，第一个卡哥的贪心

class Solution {public int maxSubArray(int[] nums) {int res = Integer.MIN_VALUE;int count = 0;for(int i = 0; i < nums.length; i++){count += nums[i];if(count > res) res = count;if(count < 0) count = 0;}return res;}
}

当我们遇到困难的时候（负数）不要逃避（跳过负数），我们试着去接受它（加入连续和），然后尝试更好地未来；如果遇到了太多的伤心事（连续和变成负数了），那都是些没有办法改变的事情，我们不如卸下包袱（连续和归0），然后奔赴一个新的起点（新的连续和起点）

第二个灵神的前缀和

class Solution {public int maxSubArray(int[] nums) {int ans = Integer.MIN_VALUE;int minPreSum = 0;int preSum = 0;for (int x : nums) {preSum += x; // 当前的前缀和ans = Math.max(ans, preSum - minPreSum); // 减去前缀和的最小值minPreSum = Math.min(minPreSum, preSum); // 维护前缀和的最小值}return ans;}
}作者：灵茶山艾府

由于子数组的元素和等于两个前缀和的差，所以求出 nums 的前缀和，问题就变成 121. 买卖股票的最佳时机 了。本题子数组不能为空，相当于一定要交易一次。

我们可以一边遍历数组计算前缀和，一边维护前缀和的最小值（相当于股票最低价格），用当前的前缀和（卖出价格）减去前缀和的最小值（买入价格），就得到了以当前元素结尾的子数组和的最大值（利润），用它来更新答案的最大值（最大利润）。

请注意，由于题目要求子数组不能为空，应当先计算前缀和-最小前缀和，再更新最小前缀和。相当于不能在同一天买入股票又卖出股票。

如果先更新最小前缀和，再计算前缀和-最小前缀和，就会把空数组的元素和 0 算入答案。

1. 前缀和是专门用来计算子数组和的，按照题解最上面的讲解，子数组和可以表示为两个前缀和的差，即 s[j] - s[i]。
2. 枚举 j，为了让 s[j] - s[i] 尽量大，那么 s[i] 需要尽量小，所以要维护前缀和的最小值

有负数不能滑窗，可以做做 560. 和为 K 的子数组

第三个方法动态规划，但时候学了再补充。