代码随想录算法训练营Day27 | 455.分发饼干| 376. 摆动序列 | 53. 最大子数组和

今日任务

455.分发饼干

• 题目链接： https://leetcode.cn/problems/assign-cookies/
• 题目描述：
  

Code

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        int ans = 0;
        ranges::sort(g);
        ranges::sort(s);
        int i = 0;
        for(int t : g){
            while(i < s.size() && s[i] < t){
                i++;
            }
            if(i >= s.size()){
                break;
            }
            i++;
            ans++;
        }
        return ans;
    }
};

376. 摆动序列

• 题目链接： https://leetcode.cn/problems/wiggle-subsequence/description/
• 题目描述：

Code

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        if(n < 2 || n == 2 && nums[0] != nums[1]){
            return n;
        }
        // int prev = 0;
        // int ans = 1;
        // for(int i = 1; i < n; i++){
        //     if(nums[i] == nums[i - 1]){
        //         continue;
        //     }
        //     int cur = nums[i] > nums[i - 1] ? 1 : -1;
        //     ans += cur != prev;
        //     prev = cur;
        // }

        strong_ordering pre = strong_ordering::equal;
        int ans = 1;
        for(int i = 1; i < n; i++){
            if(nums[i] == nums[i - 1]){
                continue;
            }
            auto cur = nums[i] <=> nums[i - 1];
            ans += cur != pre;
            pre = cur;
        }
        return ans;
    }
};

53. 最大子数组和

• 题目链接： https://leetcode.cn/problems/maximum-subarray/description/
• 题目描述：
  

Code

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // int ans = INT_MIN;
        // int min_pre_sum = 0;
        // int pre_sum = 0;
        // for(int t : nums){
        //     pre_sum += t;
        //     ans = max(ans, pre_sum - min_pre_sum);
        //     min_pre_sum = min(min_pre_sum, pre_sum);
        // }
        // return ans;

        // int n = nums.size();
        // vector<int> f(n);
        // f[0] = nums[0];
        // for(int i = 1; i < n; i++){
        //     f[i] = max(f[i - 1], 0) + nums[i];
        // }
        // return ranges::max(f);

        int ans = INT_MIN;
        int f = 0;
        for(int t : nums){
            f = max(f, 0) + t;
            ans = max(ans, f);
        }
        return ans;
    }
};