算法训练Day31|理论基础 ● 455.分发饼干 ● 376. 摆动序列 ● 53. 最大子序和

 1class Solution {
 2    public int findContentChildren(int[] g, int[] s) {
 3        int count = 0;
 4        Arrays.sort(g);
 5        Arrays.sort(s);
 6        for (int i = s.length - 1; i >= 0; i--) {
 7            for (int j = g.length - 1; j >= 0; j--) {
 8                if (s[i] >= g[i]) {
 9                    count++;
10                    break;
11                }
12            }
13        }
14        return count;
15        // 计数器计数
16    }
17}

 1class Solution {
 2    public int wiggleMaxLength(int[] nums) {
 3        if (nums.length <= 1) {
 4            return nums.length;
 5        }
 6        int curDiff = 0;
 7        int preDiff = 0;
 8        int count = 1;
 9        for (int i = 1; i < nums.length; i++) {
10            curDiff = nums[i] - nums[i - 1];
11            // 这里=只能给preDiff，curDiff上面被赋值之后，有可能会发生改变
12            if ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)) { 
13                count++;
14                preDiff = curDiff;
15            }
16        }
17        return count;
18    }
19}

 1// 暴力解法
 2class Solution {
 3    public int maxSubArray(int[] nums) {
 4        // 找到连续子数组，分别计算范围内的和，比较各个和
 5        int result = Integer.MIN_VALUE;
 6        for (int i = 0; i < nums.length; i++) {
 7            int curSum = 0;
 8            for (int j = i; j < nums.length; j++) {
 9                curSum += nums[j];
10                result = Math.max(result, curSum);
11            }
12        }
13        return result;
14    }
15}

 1// 贪心算法：剪枝操作
 2class Solution {
 3    public int maxSubArray(int[] nums) {
 4        int result = Integer.MIN_VALUE;
 5        int curSum = 0;
 6        for (int i = 0; i < nums.length; i++) {
 7            curSum += nums[i];
 8            result = Math.max(result, curSum);
 9            // 当前和为<= 0 时，剪枝操作
10            if (curSum <= 0) {
11                curSum = 0;
12            }
13        }
14        return result;
15    }
16}