算法训练营第二十八天（8.11）

目录

LeeCode 455. Assign Cookies

 LeeCode 376. Wiggle Subsequence

 LeeCode 53. Maximum Subarray

LeeCode 455. Assign Cookies

题目地址：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目类型：贪心

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int i = 0, j = 0;
        int sum = 0;
        while (i < g.size() && j < s.size()) {
            if (g[i] <= s[j]) {
                i++;
                j++;
                sum++;
            }
            else {
                j++;
            }
        }
        return sum;
    }
};

 LeeCode 376. Wiggle Subsequence

题目地址：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目类型：贪心

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if (nums.size() == 1) return 1;
        int prediff = 0, curdiff = 0, ans = 1;
        for (int i = 0; i < nums.size() - 1; ++i) {
            curdiff = nums[i + 1] - nums[i];
            if ((prediff >= 0 && curdiff < 0) || (prediff <= 0 && curdiff > 0)) {
                ans++;
                prediff = curdiff;
            }
        }
        return ans;
    }
};

 LeeCode 53. Maximum Subarray

题目地址：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目类型：贪心

class Solution {
public:
    // f(i) = max(f(i - 1) + nums[i], nums[i])，表示以第i个元素结尾的子数组的最大和值
    int maxSubArray(vector<int>& nums) {
        int pre = 0, ans = INT_MIN;
        for (int &num : nums) {
            pre = max(pre + num, num);
            ans = max(ans, pre);
        }
        return ans;
    }
};