代码随想录算法训练营第三十一天| 455.分发饼干，376. 摆动序列 ，53. 最大子序和
455. 分发饼干 - 力扣（LeetCode）
class Solution {public int findContentChildren(int[] g, int[] s) {Arrays.sort(g); //递增Arrays.sort(s); int result = 0;//遍历，先满足小的int i=0,j=0;for(;i<g.length && j<s.length;i++){while (j<s.length && s[j]<g[i]){j++; }if(j >= s.length){break;}result++;j++;}return result;}
}376. 摆动序列 - 力扣（LeetCode）
class Solution {public int wiggleMaxLength(int[] nums) {if(nums.length == 1 || (nums.length ==2 && nums[0] != nums[1])){return nums.length;}int prevState = 0;int nowState = 0;int result = 1;for(int i=1;i<nums.length;i++){if(nums[i] == nums[i-1]){continue;}else if(nums[i] < nums[i-1]){nowState = 1;}else{nowState = -1;}if(nowState != prevState){result++;}prevState = nowState;}return result;}
} 53. 最大子数组和 - 力扣（LeetCode）
class Solution {// 贪心算法求解public int maxSubArray(int[] nums) {if(nums.length == 0){return 0;}int sum = nums[0];int result = nums[0];for(int i=1;i<nums.length;i++){if(sum + nums[i] < nums[i]){sum = nums[i];}else{sum = sum + nums[i];}result = Math.max(result,sum);}return result;}// DP算法// public int maxSubArray(int[] nums) {// if (nums.length == 0) {// return 0;// }// int[] dp = new int[nums.length];// dp[0] = nums[0];// int result = nums[0];// for (int i = 1; i < nums.length; i++) {// if (dp[i - 1] >= 0) {// dp[i] = dp[i - 1] + nums[i];// } else {// dp[i] = nums[i];// }// result = Math.max(result, dp[i]);// }// return result;// }
}