算法练习Day25 （Leetcode/Python-贪心算法）
贪心算法基本概念：
贪心的本质是通过选取局部最优达到全局最优。
并没有固定的套路，检验的算法正确性的办法可以是举反例。
455. Assign Cookies
Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie.
Each child i has a greed factor g[i], which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s[j]. If s[j] >= g[i], we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.
Example 1:
Input: g = [1,2,3], s = [1,1] Output: 1 Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3. And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content. You need to output 1.
思路：分饼干，一个饼干最多分给一个人，若饼干大小>=孩子胃口则该孩子获得满足，设计算法尽可能满足更多的孩子。
这道题用贪心算法做，先对饼干和孩子排序。可以从大饼干和胃口大的孩子开始遍历，本着不浪费的原则，大饼干优先满足大胃口的孩子，对于每一块饼干，将胃口从大到小的孩子和它一一对应，如果满足了一个孩子，则move to下一块次大的饼干。
class Solution(object):def findContentChildren(self, g, s):""":type g: List[int] # children :type s: List[int] # cookies:rtype: int"""g.sort() # small to large s.sort() # small to large j = len(s) - 1 # cookiesmatched = 0for i in range(len(g) - 1, -1, -1):if j < 0: # Check if there are any cookies leftbreakif s[j] >= g[i]: # If the current cookie satisfies the appetite, move to the next cookiematched += 1j -= 1return matched时间复杂度的分析：
sort：O(nlogn)，O(mlogm)。n和m分别为人和饼干的个数
for循环：O(n)。
Overall：O(nlogn) + O(mlogm)。对于较小的n值，O(n)和O(n log n)可能相当接近。但随着n的增大，O(n log n)的增长速度将超过O(n)。
53. Maximum Subarray
Given an integer array nums, find the
subarray
with the largest sum, and return its sum.
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: The subarray [4,-1,2,1] has the largest sum 6.
思路：求最大连续子序列之和。暴力解法O(n^2)的复杂度，做两次循环，遍历所有可能的子序列。但是也可以用一个count逐位累加，在这个过程中不断更新max_count的值。若累加值为负数，则清空重开一局，也就是以之后一个元素为新的子序列开头，防止之前子序列的负数造成拖累。
class Solution(object):def maxSubArray(self, nums):""":type nums: List[int]:rtype: int"""count = 0max_count = float('-inf') # 注意这里是float('-inf')而不是0，有可能最大和也是是负数。for i in range(len(nums)):count += nums[i]if count > max_count: # 注意这两个if的顺序不可以颠倒max_count = countif count <= 0: # 若当前子序列累加和都小于0了，对继续延长的序列的也是拖累，不如重新开始。# 重新开始计数之前这个子序列的最大和已经被记录下来了。count = 0 return max_count # 时间复杂度O(n)