贪心1.
贪心一言以蔽之，就是局部最优=>全局最优。并没有什么套路，只能是肉眼看出局部最优，然后想一下有没有反例（即局部最优推不出全局最优的例子）。如果想不出反例那就可以试试。
要证明贪心算法的正确性，一般是反证法或者数学归纳法。我记得算法课里反证法好像用得比较多的。可以了解一下，不过面试的话一般不会让证明贪心的正确性的。
个人用的是最小剩余饼干分给最小胃口的剩余孩子这个策略。可以用反证法证明。
这里的贪心策略是跳过单调序列中间的元素。
3711第一课。我挑了一个非贪心里面复杂度最优的解法，用前缀和，遍历前缀和数组并记录当前元素与之前最小元素的差值。
以下代码的时间是O(n)，空间是O(1)，但是只击败了16%的用户。
def maxSubArray(self, nums: List[int]) -> int:
for i in range(1, len(nums)):
nums[i] += nums[i-1]
min = 0
best = -inf
for j in nums:
if j - min > best:
best = j - min
if j < min:
min = j
return best
所以说另外用户应该都是用的贪心。贪心的思想就是发现当前区间之和为负数时抛弃当前区间，因为负数和只会拖累整个区间和。
def maxSubArray(self, nums: List[int]) -> int:
best = -inf
sum = 0
for num in nums:
sum += num
if sum > best:
best = sum
if sum < 0:
sum = 0
return best
可以看到贪心的形式非常多样，很难说有什么套路。
像最后两题的共同点都是“舍弃”没有用的部分，比如单调序列的中间元素和区间和和为负数的区间。这都要具体问题具体分析。