# 本周小结！（贪心算法系列一）
# 周一
本周正式开始了贪心算法，在关于贪心算法，你该了解这些！ (opens new window)中，我们介绍了什么是贪心以及贪心的套路。
贪心的本质是选择每一阶段的局部最优，从而达到全局最优。
有没有啥套路呢？
不好意思，贪心没套路，就刷题而言，如果感觉好像局部最优可以推出全局最优，然后想不到反例，那就试一试贪心吧！
而严格的数据证明一般有如下两种：
- 数学归纳法
- 反证法
数学就不在讲解范围内了，感兴趣的同学可以自己去查一查资料。
正是因为贪心算法有时候会感觉这是常识，本就应该这么做！ 所以大家经常看到网上有人说这是一道贪心题目，有人说这不是。
这里说一下我的依据：如果找到局部最优，然后推出整体最优，那么就是贪心，大家可以参考哈。
# 周二
在贪心算法：分发饼干 (opens new window)中讲解了贪心算法的第一道题目。
这道题目很明显能看出来是用贪心，也是入门好题。
我在文中给出局部最优：大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优：喂饱尽可能多的小孩。
很多录友都是用小饼干优先先喂饱小胃口的。
后来我想一想，虽然结果是一样的，但是大家的这个思考方式更好一些。
因为用小饼干优先喂饱小胃口的 这样可以尽量保证最后省下来的是大饼干（虽然题目没有这个要求）！
所以还是小饼干优先先喂饱小胃口更好一些，也比较直观。
一些录友不清楚贪心算法：分发饼干 (opens new window)中时间复杂度是怎么来的？
就是快排O(nlog n)，遍历O(n)，加一起就是还是O(nlogn)。
# 周三
接下来就要上一点难度了，要不然大家会误以为贪心算法就是常识判断一下就行了。
在贪心算法：摆动序列 (opens new window)中，需要计算最长摇摆序列。
其实就是让序列有尽可能多的局部峰值。
局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。
整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。
在计算峰值的时候，还是有一些代码技巧的，例如序列两端的峰值如何处理。
这些技巧，其实还是要多看多用才会掌握。
# 周四
在贪心算法：最大子序和 (opens new window)中，详细讲解了用贪心的方式来求最大子序列和，其实这道题目是一道动态规划的题目。
贪心的思路为局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。从而推出全局最优：选取最大“连续和”
代码很简单，但是思路却比较难。还需要反复琢磨。
针对贪心算法：最大子序和 (opens new window)文章中给出的贪心代码如下；
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int result = INT32_MIN;
int count = 0;
for (int i = 0; i < nums.size(); i++) {
count += nums[i];
if (count > result) { // 取区间累计的最大值（相当于不断确定最大子序终止位置）
result = count;
}
if (count <= 0) count = 0; // 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
}
return result;
}
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
不少同学都来问，如果数组全是负数这个代码就有问题了，如果数组里有int最小值这个代码就有问题了。
大家不要脑洞模拟哈，可以亲自构造一些测试数据试一试，就发现其实没有问题。
数组都为负数，result记录的就是最大的负数，如果数组里有int最小值，那么最终result就是int最小值。
# 总结
本周我们讲解了贪心算法的理论基础 (opens new window)，了解了贪心本质：局部最优推出全局最优。
然后讲解了第一道题目分发饼干 (opens new window)，还是比较基础的，可能会给大家一种贪心算法比较简单的错觉，因为贪心有时候接近于常识。
其实我还准备一些简单的贪心题目，甚至网上很多都质疑这些题目是不是贪心算法。这些题目我没有立刻发出来，因为真的会让大家感觉贪心过于简单，而忽略了贪心的本质：局部最优和全局最优两个关键点。
所以我在贪心系列难度会有所交替，难的题目在于拓展思路，简单的题目在于分析清楚其贪心的本质，后续我还会发一些简单的题目来做贪心的分析。
在摆动序列 (opens new window)中大家就初步感受到贪心没那么简单了。
本周最后是最大子序和 (opens new window)，这道题目要用贪心的方式做出来，就比较有难度，都知道负数加上正数之后会变小，但是这道题目依然会让很多人搞混淆，其关键在于：不能让“连续和”为负数的时候加上下一个元素，而不是 不让“连续和”加上一个负数。这块真的需要仔细体会！
