# Day 31 | 贪心算法 理论基础 、455.分发饼干 、 376. 摆动序列 、 53. 最大子序和

## 455.分发饼干

``````class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int start = 0;
int count = 0;
for (int i = 0; i < s.length && start < g.length; i++) {
if (s[i] >= g[start]) {
start++;
count++;
}
}
return count;
}
}
``````

## 376. 摆动序列

``````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];
//等于0的情况表示初始时的preDiff
if (curDIff < 0 && preDIff >= 0 || curDIff > 0 && preDIff <= 0){
count++;
preDIff = curDIff;
}
}
return count;
}
}
``````

## 53. 最大子序和

``````class Solution {
public int maxSubArray(int[] nums) {
if (nums.length == 1){
return nums[0];
}
int sum = Integer.MIN_VALUE;
int count = 0;
for (int i = 0; i < nums.length; i++){
count += nums[i];
sum = Math.max(sum, count); // 取区间累计的最大值（相当于不断确定最大子序终止位置）
if (count <= 0){
count = 0; // 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
}
}
return sum;
}
}
``````

THE END