代码随想录算法训练营第三十一天| 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;
    // }
}