贪心算法并没有固定的套路，就是如何通过局部最优，推出整体最优。一般分为如下四步：
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
例一：455.分发饼干
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
输入: g = [1,2,3], s = [1,1]
输出: 1
解释:
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。
class Solution(object):
def findContentChildren(self, g, s):
"""
:type g: List[int]
:type s: List[int]
:rtype: int
"""
#胃口小的孩子先用小饼干满足
res=0
m=len(g)
n=len(s)
g.sort()
s.sort()
i=0
j=0
while j<n and i<m:
if s[j]>=g[i]:
res+=1
i+=1
j+=1
else:
j+=1
return res
例二.376. 摆动序列
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。
输入：nums = [1,7,4,9,2,5]
输出：6
解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。
class Solution(object):
def wiggleMaxLength(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
# ##贪心算法
# #局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。
# #全局最优：删掉单调坡度上的节点（不包括单调坡度两端的节点），保留其他局部峰值
##容易错在细节：怎么处理示例如1 2 3 4 5 和0 0 0 或者3 3 3 2 5
#注意：这里讲的是子序列而不是连续子序列，注意区分
#错误版本:1 7 4 9 2 5示例过不了，对于第一个数的处理和最后一个数的处理需要注意 对于重复数字处理需要注意
# n=len(nums)
# if n==1:
# return 1
# if n==2:
# if nums[0]==nums[1]:
# return 1
# return 2
# res=1 #初始化res=1的理由：只要序列不为空，res最小为1
# for i in range(1,n-1):
# if (nums[i+1]-nums[i]>0 and nums[i]-nums[i-1]<=0) or (nums[i+1]-nums[i]<0 and nums[i]-nums[i-1]>=0):
# res+=1
# # print(i)
# # print(res)
# return res
## 正确版本贪心
#对于3 3 3 2 5序列的处理
n=len(nums)
curdiff=0
prediff=0 #对于第一个数的处理，[2,5]处理成[2,2,5]，prediff=2-2=0 这样第一个2可以被作为一个局部峰值
res=1
for i in range(n-1):
curdiff=nums[i+1]-nums[i]
if (curdiff>0 and prediff<=0) or (curdiff<0 and prediff>=0):
res+=1
prediff=curdiff
return res
#动态规划
#难点：想不到用二维dp来做，对每个nums[i],用两个数来分别存储当它作为山谷与作为山峰时的摆动子序列的最长长度
#陷在了dp[i]怎么来表示的困境，也没有想到对nums[i]分山谷和山峰两种情况考虑
#dp[i][0]，表示考虑前i个数，第i个数作为山谷的摆动子序列的最长长度
#dp[i][1]，表示考虑前i个数，第i个数作为山峰的摆动子序列的最长长度
dp=[[0 for _ in range(2)] for _ in range(n)]
dp[0][0]=1
dp[0][1]=1
for i in range(1,n):
dp[i][0]=1
dp[i][1]=1
for j in range(i):
if nums[i]<nums[j]: #求nums[i]作为山谷时的最大摆动子序列长度，使用dp[j][1]+1来更新
dp[i][0]=max(dp[i][0],dp[j][1]+1)
if nums[i]>nums[j]: #同理
dp[i][1]=max(dp[i][1],dp[j][0]+1)
return max(dp[n-1][0],dp[n-1][1]) #返回最后一个数分别作为山谷和山峰时的最长长度
例三.53. 最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
## 动态规划
#dp[i]:nums[i]位置的最大连续子数组和 dp[i]=max(dp[i-1]+nums[i],nums[i])
#递推公式中max(dp[i-1]+nums[i],nums[i])说明对比nums[i]和dp[i-1]+nums[i]哪个更大，其实和贪心算法的如果连续子数组和是负数，则抛弃重新计数一个道理
n=len(nums)
dp=[0]*(n)
dp[0]=nums[0]
res=nums[0]
for i in range(1,n):
dp[i]=max(dp[i-1]+nums[i],nums[i])
if dp[i]>res:
res=dp[i]
return res
# "暴力算法."
# "对于每个nums[i],j从每个i开始数、开始加，如果加出来的数大于之前加出来最大的数，就把最大数替换，这样循环下来就可以找到加出来的最大数"
n=len(nums)
if n==1:
return nums[0]
maxmum=-1e9
for i in range(n):
sum=0
for j in range(i,n):
sum+=nums[j]
if sum>maxmum:
maxmum=sum
return maxmum
#贪心算法
#局部最优：如果连续子数组和是负数，则抛弃
res=nums[0]
n=len(nums)
if n==1:
return res
tmp=nums[0] #连续子数组和
for i in range(1,n):
if tmp>=0:
tmp+=nums[i]
else:
tmp=nums[i] #如果连续子数组和是负数，从当前位置重新算
if tmp>res:
res=tmp
return res
例四. 122. 买卖股票的最佳时机 II
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
#动态规划
#对于每天i，可以选择买入、卖出、不操作三种选项，存在两种状态
#dp[i][0] 第i天持有股票后的最多现金（不操作、买入）
#dp[i][1] 第i天持有的最多现金（不操作、卖出）
#对于每个i都更新这两个状态
n=len(prices)
dp=[[0 for _ in range(2)] for _ in range(n)]
dp[0][0]-=prices[0]
dp[0][1]=0
for i in range(1,n):
#第i天持股票所剩最多现金 = max(第i-1天持股票所剩现金, 第i-1天持现金-买第i天的股票)
dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i])
# 第i天持有最多现金 = max(第i-1天持有的最多现金，第i-1天持有股票的最多现金+第i天卖出股票)
dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i])
return max(dp[n-1][0],dp[n-1][1])
#贪心算法
#对每一个点，都有买入、卖出、不操作三种选项。山谷买入、山峰卖出、斜坡上不操作
#需要考虑削平的山峰和山谷怎么处理 比如[2 1 2 1 0 0 1]
#所以买入点是prices[i]<=prices[i-1] and prices[i]<prices[i+1]
#卖出点是prices[i]>prices[i-1] and prices[i]>=prices[i+1]
n=len(prices)
res=0
buy=0 #默认起点卖出，如果不是，buy后续会被覆盖
sell=0
for i in range(1,n-1):
if prices[i]<=prices[i-1] and prices[i]<prices[i+1]:
buy=i
if prices[i]>prices[i-1] and prices[i]>=prices[i+1]:
sell=i
res+=prices[sell]-prices[buy]
if prices[n-1]>prices[n-2]:
sell=n-1
res+=prices[sell]-prices[buy]
return res
例五：55. 跳跃游戏
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
class Solution(object):
def canJump(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
#贪心算法：
#关键点在于：不用拘泥于每次究竟跳跳几步，而是看覆盖范围，覆盖范围内一定是可以跳过来的，不用管是怎么跳的。
n=len(nums)
startpos=0 #刚开始的出发点和能到达的最远点
maxpos=nums[0]
#首先，求出每个点可以到达的最远方
farthestpos=[]
for i in range(n):
farthestpos.append(nums[i]+i)
while maxpos<n-1:
winmax=max(farthestpos[startpos:maxpos+1]) #框框里可以跳的最远的位置
if maxpos>=winmax: #如果最远并没有比当前点更远
return False
maxpos=winmax
startpos=farthestpos[startpos:maxpos+1].index(winmax) #返回最大值位置
return True
#贪心算法简化版代码
# 没必要用两次循环，可以简化为一次，并且可以直接返回i减少.index()函数的使用，节约用时
n=len(nums)
if n==1:
return True
cover=0
i=0
#这里需要注意： python不支持动态修改for循环中变量,使用while循环代替
while i<=cover:
cover=max(nums[i]+i,cover)
if cover>=n-1:
return True
i+=1
return False
例六.45. 跳跃游戏 II
给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
class Solution(object):
def jump(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
#贪心算法
#方法一思路：由于题目给出总是可以到达数组的最后一个位置，需要从后往前推到到下标为0的起点
#能达到目标位置的节点越靠前，总跳数越少
#cover记载跳的位置，每次都从前往后找到最靠前的能到达cover位置的下标，记载成为一跳
n=len(nums)
cover=n-1
res=0
while cover>0:
for i in range(n):
if nums[i]+i>=cover:
cover=i
res+=1
break
return res
# 方法二思路
# 从前往后，移动下标达到了当前覆盖的最远距离下标时，步数就要加一
n=len(nums)
curpos=0 # 当前覆盖最远距离下标
nextpos=0 #记录下一步最远距离下标
res=0
for i in range(n):
nextpos=max(nums[i]+i,nextpos)
if i==curpos: #遇到当前覆盖最远距离下标
if curpos!=n-1: #如果当前覆盖最远距离下标不是终点,需要走下一步
res+=1
curpos=nextpos
if curpos>=n-1:
break
else:
break
return res
#方法二简化版
#控制移动下标i只移动到n - 2的位置，所以移动下标只要遇到当前覆盖最远距离的下标，直接步数加一，不用考虑别的了
#当移动下标i指向n - 2时,如果移动下标等于当前覆盖最大距离下标， 需要再走一步;
#如果移动下标不等于当前覆盖最大距离下标，说明当前覆盖最远距离就可以直接达到终点了
n=len(nums)
curpos=0 # 当前覆盖最远距离下标
nextpos=0 #记录下一步最远距离下标
res=0
for i in range(n-1):
nextpos=max(nums[i]+i,nextpos)
if i==curpos: #遇到当前覆盖最远距离下标
res+=1
curpos=nextpos
return res
例七.1005. K 次取反后最大化的数组和
给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
以这种方式修改数组后，返回数组 可能的最大和 。
输入：nums = [4,2,3], k = 1
输出：5
解释：选择下标 1 ，nums 变为 [4,-2,3] 。
#第一步：将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
#第二步：从前向后遍历，遇到负数将其变为正数，同时K--
#第三步：如果K还大于0，那么反复转变数值最小的元素，将K用完
#第四步：求和
class Solution(object):
def largestSumAfterKNegations(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
#考虑（-1，2） k=2
n=len(nums)
nums.sort() #
for i in range(n):
if nums[i]<0:
nums[i]=-nums[i]
k-=1
if k<=0:
break
nums.sort()
if k>0:
if k%2==0:
k=0
else:
nums[0]=-nums[0]
return sum(nums)
