
# 本周小结！（贪心算法系列一）

## 周一

本周正式开始了贪心算法，在[关于贪心算法，你该了解这些！](https://programmercarl.com/贪心算法理论基础.html)中，我们介绍了什么是贪心以及贪心的套路。

**贪心的本质是选择每一阶段的局部最优，从而达到全局最优。**

有没有啥套路呢？

**不好意思，贪心没套路，就刷题而言，如果感觉好像局部最优可以推出全局最优，然后想不到反例，那就试一试贪心吧！**

而严格的数据证明一般有如下两种：

* 数学归纳法
* 反证法

数学就不在讲解范围内了，感兴趣的同学可以自己去查一查资料。

正式因为贪心算法有时候会感觉这是常识，本就应该这么做！ 所以大家经常看到网上有人说这是一道贪心题目，有人是这不是。

这里说一下我的依据：**如果找到局部最优，然后推出整体最优，那么就是贪心**，大家可以参考哈。

## 周二


在[贪心算法：分发饼干](https://programmercarl.com/0455.分发饼干.html)中讲解了贪心算法的第一道题目。

这道题目很明显能看出来是用贪心，也是入门好题。

我在文中给出**局部最优：大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优：喂饱尽可能多的小孩**。

很多录友都是用小饼干优先先喂饱小胃口的。

后来我想一想，虽然结果是一样的，但是大家的这个思考方式更好一些。

**因为用小饼干优先喂饱小胃口的 这样可以尽量保证最后省下来的是大饼干（虽然题目没有这个要求）！**

所有还是小饼干优先先喂饱小胃口更好一些，也比较直观。

一些录友不清楚[贪心算法：分发饼干](https://programmercarl.com/0455.分发饼干.html)中时间复杂度是怎么来的？

就是快排$O(n\log n)$，遍历$O(n)$，加一起就是还是$O(n\log n)$。

## 周三

接下来就要上一点难度了，要不然大家会误以为贪心算法就是常识判断一下就行了。

在[贪心算法：摆动序列](https://programmercarl.com/0376.摆动序列.html)中，需要计算最长摇摆序列。

其实就是让序列有尽可能多的局部峰值。

局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。

整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。

在计算峰值的时候，还是有一些代码技巧的，例如序列两端的峰值如何处理。

这些技巧，其实还是要多看多用才会掌握。


## 周四

在[贪心算法：最大子序和](https://programmercarl.com/0053.最大子序和.html)中，详细讲解了用贪心的方式来求最大子序列和，其实这道题目是一道动态规划的题目。

**贪心的思路为局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。从而推出全局最优：选取最大“连续和”**

代码很简单，但是思路却比较难。还需要反复琢磨。

针对[贪心算法：最大子序和](https://programmercarl.com/0053.最大子序和.html)文章中给出的贪心代码如下；
```
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;
    }
};
```
不少同学都来问，如果数组全是负数这个代码就有问题了，如果数组里有int最小值这个代码就有问题了。

大家不要脑洞模拟哈，可以亲自构造一些测试数据试一试，就发现其实没有问题。

数组都为负数，result记录的就是最小的负数，如果数组里有int最小值，那么最终result就是int最小值。


## 总结

本周我们讲解了[贪心算法的理论基础](https://programmercarl.com/贪心算法理论基础.html)，了解了贪心本质：局部最优推出全局最优。

然后讲解了第一道题目[分发饼干](https://programmercarl.com/0455.分发饼干.html)，还是比较基础的，可能会给大家一种贪心算法比较简单的错觉，因为贪心有时候接近于常识。

其实我还准备一些简单的贪心题目，甚至网上很多都质疑这些题目是不是贪心算法。这些题目我没有立刻发出来，因为真的会让大家感觉贪心过于简单，而忽略了贪心的本质：局部最优和全局最优两个关键点。

**所以我在贪心系列难度会有所交替，难的题目在于拓展思路，简单的题目在于分析清楚其贪心的本质，后续我还会发一些简单的题目来做贪心的分析。**

在[摆动序列](https://programmercarl.com/0376.摆动序列.html)中大家就初步感受到贪心没那么简单了。

本周最后是[最大子序和](https://programmercarl.com/0053.最大子序和.html)，这道题目要用贪心的方式做出来，就比较有难度，都知道负数加上正数之后会变小，但是这道题目依然会让很多人搞混淆，其关键在于：**不能让“连续和”为负数的时候加上下一个元素，而不是 不让“连续和”加上一个负数**。这块真的需要仔细体会！






<div align="center"><img src=https://code-thinking.cdn.bcebos.com/pics/01二维码.jpg width=450> </img></div>
