贪心算法455|376|53

455分发饼干

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        index = len(s) - 1
        num = 0
        for i in range(len(g) - 1, -1, -1):
            if index >= 0 and s[index] >= g[i]:
                num += 1
                index -= 1
        return num

376摆动序列

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        unique_num = []
        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            unique_num.append(nums[i])
        
        result = 1
        prediff = 0
        curdiff = 0
        for i in range(len(unique_num) - 1):
            curdiff = unique_num[i + 1] - unique_num[i]
            if (prediff <= 0 and curdiff > 0) or (prediff >= 0 and curdiff < 0):
                result += 1
            prediff = curdiff
        return result

53最大子数组和

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        result = float('-inf')
        cur_sum = 0
        for item in nums:
            if cur_sum < 0:
                cur_sum = item
            else:
                cur_sum += item
            if cur_sum > result:
                result = cur_sum
        return result