本节内容

理论基础
455.分发饼干
1. 摆动序列
1. 最大子序和

贪心算法其实就是没有什么规律可言，所以了解贪心算法就了解它没有规律的本质就够了。

不用花心思去研究其规律，没有思路就立刻看题解。

基本贪心的题目有两个极端，要不就是特简单，要不就是死活想不出来。

学完贪心之后再去看动态规划，就会了解贪心和动规的区别。

理论基础※

https://programmercarl.com/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

什么是贪心

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

贪心的套路（什么时候用贪心）

很多同学做贪心的题目的时候，想不出来是贪心，想知道有没有什么套路可以一看就看出来是贪心。

说实话贪心算法并没有固定的套路。

所以唯一的难点就是如何通过局部最优，推出整体最优。

那么如何能看出局部最优是否能推出整体最优呢？有没有什么固定策略或者套路呢？

不好意思，也没有！ 靠自己手动模拟，如果模拟可行，就可以试一试贪心策略，如果不可行，可能需要动态规划。

有同学问了如何验证可不可以用贪心算法呢？

最好用的策略就是举反例，如果想不到反例，那么就试一试贪心吧。

可有有同学认为手动模拟，举例子得出的结论不靠谱，想要严格的数学证明。

一般数学证明有如下两种方法：

数学归纳法
反证法

面试中基本不会让面试者现场证明贪心的合理性，代码写出来跑过测试用例即可，或者自己能自圆其说理由就行了。

刷题或者面试的时候，手动模拟一下感觉可以局部最优推出整体最优，而且想不到反例，那么就试一试贪心。

贪心一般解题步骤

贪心算法一般分为如下四步：

将问题分解为若干个子问题
找出适合的贪心策略
求解每一个子问题的最优解
将局部最优解堆叠成全局最优解

这个四步其实过于理论化了，我们平时在做贪心类的题目很难去按照这四步去思考，真是有点“鸡肋”。

做题的时候，只要想清楚局部最优是什么，如果推导出全局最优，其实就够了。

455.分发饼干※

建议：

题目链接： https://leetcode.cn/problems/assign-cookies/
文章讲解： https://programmercarl.com/0455.%E5%88%86%E5%8F%91%E9%A5%BC%E5%B9%B2.html
视频讲解：

题目分析

方案一

尝试一下暴力求解

class Solution {
    public int findContentChildren(int[] g, int[] s) {

        // 暴力求解一下
        int result = 0;
        int index = -1;
        int temp = Integer.MAX_VALUE;

        for (int i = 0; i < g.length; i++) {
            index = -1;
            temp = Integer.MAX_VALUE;

            for (int j = 0; j < s.length; j++) {
                if (s[j] >= g[i] && temp >= s[j]){
                    temp = s[j];
                    index = j;
                }
            }

            if (index != -1) {
                result++;
                s[index] = 0;
            }
        }

        return result;
    }
}

结果

解答成功:
执行耗时:581 ms,击败了5.03% 的Java用户
内存消耗:43.1 MB,击败了46.52% 的Java用户

分析

时间复杂度：
O( n * m )

空间复杂度：
O( m )

方案二

先对数组进行排序，然后使用双指针

class Solution {
    public int findContentChildren(int[] g, int[] s) {

        // 排序，双指针
        Arrays.sort(g);
        Arrays.sort(s);
        int result = 0;

        for (int i = 0, j = 0; i < g.length && j < s.length; j++) {
            if (g[i] <= s[j]) {
                i++;
                result++;
            }
        }

        return result;
    }
}

结果

解答成功:
执行耗时:7 ms,击败了99.88% 的Java用户
内存消耗:43 MB,击败了47.61% 的Java用户

分析

时间复杂度：
O( n log(n) ) 排序算法的时间复杂度

空间复杂度：
O( m )

代码随想录

https://programmercarl.com/0455.%E5%88%86%E5%8F%91%E9%A5%BC%E5%B9%B2.html

思路

为了满足更多的小孩，就不要造成饼干尺寸的浪费。

大尺寸的饼干既可以满足胃口大的孩子也可以满足胃口小的孩子，那么就应该优先满足胃口大的。

这里的局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩。

可以尝试使用贪心策略，先将饼干数组和小孩数组排序。

然后从后向前遍历小孩数组，用大饼干优先满足胃口大的，并统计满足小孩数量。

如图：

这个例子可以看出饼干 9 只有喂给胃口为 7 的小孩，这样才是整体最优解，并想不出反例，那么就可以撸代码了。

C++代码整体如下：

// 版本一
class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int index = s.size() - 1; // 饼干数组的下标
        int result = 0;
        for (int i = g.size() - 1; i >= 0; i--) { // 遍历胃口
            if (index >= 0 && s[index] >= g[i]) { // 遍历饼干
                result++;
                index--;
            }
        }
        return result;
    }
};

时间复杂度：O(nlogn)
空间复杂度：O(1)

从代码中可以看出我用了一个 index 来控制饼干数组的遍历，遍历饼干并没有再起一个 for 循环，而是采用自减的方式，这也是常用的技巧。

有的同学看到要遍历两个数组，就想到用两个 for 循环，那样逻辑其实就复杂了。

注意事项

注意版本一的代码中，可以看出来，是先遍历的胃口，在遍历的饼干，那么可不可以先遍历饼干，在遍历胃口呢？

其实是不可以的。

外面的 for 是里的下标 i 是固定移动的，而 if 里面的下标 index 是符合条件才移动的。

如果 for 控制的是饼干， if 控制胃口，就是出现如下情况：

if 里的 index 指向胃口 10， for 里的 i 指向饼干 9，因为饼干 9 满足不了胃口 10，所以 i 持续向前移动，而 index 走不到s[index] >= g[i] 的逻辑，所以 index 不会移动，那么当 i 持续向前移动，最后所有的饼干都匹配不上。

所以一定要 for 控制胃口，里面的 if 控制饼干。

其他思路

也可以换一个思路，小饼干先喂饱小胃口

代码如下：

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        int index = 0;
        for(int i = 0; i < s.size(); i++) { // 饼干
            if(index < g.size() && g[index] <= s[i]){ // 胃口
                index++;
            }
        }
        return index;
    }
};

时间复杂度：O(nlogn)
空间复杂度：O(1)

这种写法，两个循环的顺序改变了，先遍历的饼干，在遍历的胃口，这是因为遍历顺序变了，我们是从小到大遍历。

想清楚全局最优，感觉局部最优是可以推出全局最优，并想不出反例，那么就试一试贪心。

代码实现

class Solution {
    // 思路1：优先考虑饼干，小饼干先喂饱小胃口
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int start = 0;
        int count = 0;
        for (int i = 0; i < s.length && start < g.length; i++) {
            if (s[i] >= g[start]) {
                start++;
                count++;
            }
        }
        return count;
    }
}

class Solution {
    // 思路2：优先考虑胃口，先喂饱大胃口
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int count = 0;
        int start = s.length - 1;
        // 遍历胃口
        for (int index = g.length - 1; index >= 0; index--) {
            if(start >= 0 && g[index] <= s[start]) {
                start--;
                count++;
            }
        }
        return count;
    }
}

376. 摆动序列※

建议：

题目链接： https://leetcode.cn/problems/wiggle-subsequence/
文章讲解： https://programmercarl.com/0376.%E6%91%86%E5%8A%A8%E5%BA%8F%E5%88%97.html
视频讲解：

题目分析

方案一

当数组的长度小于2的时候，进行了一些的特殊判断，也在前期做了比较多的准备工作才开始进入到循环中。

本题的贪心体现在：当有连续超过3个数据递增或者递减，我去取其中的最高点或者最低点，这个遇到转折点我可以及时发现！！！

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length == 1) return 1;
        if (nums.length == 2) {
            if (nums[0] == nums[1]) return 1;
            return 2;
        }

        int result = 1,
                temp = nums[0],
                index = 1;

        boolean flag;

        while (index < nums.length && temp == nums[index]) {
            index++;
        }

        if (index == nums.length) {
            return 1;
        } else {
            result++;
            if (temp > nums[index]) flag = false;
            else flag = true;
            temp = nums[index];
        }

        for (int i = index + 1; i < nums.length; i++) {
//            System.out.println(flag + " " + temp + "----------" + nums[i]);
            if (temp == nums[i]) continue;
            if (flag) { // 此时需要找比temp小的数据
                if (temp > nums[i]) {
                    result++;
                    flag = false;
                }
                temp = nums[i]; // 此处体现了贪心，我想找到一个小一点的，
                        // 但是万一数据比我怎么办？比我大，我就变成你，为了更好的迎接下一个可能比我小的数据
            } else {
                if (temp < nums[i]) {
                    result++;
                    flag = true;

                }
                temp = nums[i];
            }
        }
        return result;
    }
}

结果

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:38.7 MB,击败了95.01% 的Java用户

分析

时间复杂度：
O( n )

空间复杂度：
O( 1 )

代码随想录

https://programmercarl.com/0376.%E6%91%86%E5%8A%A8%E5%BA%8F%E5%88%97.html

思路 1（贪心解法）

本题要求通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。

相信这么一说吓退不少同学，这要求最大摆动序列又可以修改数组，这得如何修改呢？

来分析一下，要求删除元素使其达到最大摆动序列，应该删除什么元素呢？

用示例二来举例，如图所示：

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

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

局部最优推出全局最优，并举不出反例，那么试试贪心！

（为方便表述，以下说的峰值都是指局部峰值）

实际操作上，其实连删除的操作都不用做，因为题目要求的是最长摆动子序列的长度，所以只需要统计数组的峰值数量就可以了（相当于是删除单一坡度上的节点，然后统计长度）

这就是贪心所贪的地方，让峰值尽可能的保持峰值，然后删除单一坡度上的节点

在计算是否有峰值的时候，大家知道遍历的下标 i ，计算 prediff（nums[i] - nums[i-1]）和 curdiff（nums[i+1] - nums[i]），如果prediff < 0 && curdiff > 0 或者 prediff > 0 && curdiff < 0 此时就有波动就需要统计。

这是我们思考本题的一个大题思路，但本题要考虑三种情况：

情况一：上下坡中有平坡
情况二：数组首尾两端
情况三：单调坡中有平坡

情况一：上下坡中有平坡

例如 [1,2,2,2,1]这样的数组，如图：

它的摇摆序列长度是多少呢？ 其实是长度是 3，也就是我们在删除的时候要不删除左面的三个 2，要不就删除右边的三个 2。

如图，可以统一规则，删除左边的三个 2：

在图中，当 i 指向第一个 2 的时候，prediff > 0 && curdiff = 0 ，当 i 指向最后一个 2 的时候 prediff = 0 && curdiff < 0。

如果我们采用，删左面三个 2 的规则，那么当 prediff = 0 && curdiff < 0 也要记录一个峰值，因为他是把之前相同的元素都删掉留下的峰值。

所以我们记录峰值的条件应该是： (preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)，为什么这里允许 prediff == 0 ，就是为了上面我说的这种情况。

情况二：数组首尾两端

所以本题统计峰值的时候，数组最左面和最右面如何统计呢？

题目中说了，如果只有两个不同的元素，那摆动序列也是 2。

例如序列[2,5]，如果靠统计差值来计算峰值个数就需要考虑数组最左面和最右面的特殊情况。

因为我们在计算 prediff（nums[i] - nums[i-1]）和 curdiff（nums[i+1] - nums[i]）的时候，至少需要三个数字才能计算，而数组只有两个数字。

这里我们可以写死，就是如果只有两个元素，且元素不同，那么结果为 2。

不写死的话，如何和我们的判断规则结合在一起呢？

可以假设，数组最前面还有一个数字，那这个数字应该是什么呢？

之前我们在讨论情况一：相同数字连续的时候， prediff = 0 ，curdiff < 0 或者 >0 也记为波谷。

那么为了规则统一，针对序列[2,5]，可以假设为[2,2,5]，这样它就有坡度了即 preDiff = 0，如图：

针对以上情形，result 初始为 1（默认最右面有一个峰值），此时 curDiff > 0 && preDiff <= 0，那么 result++（计算了左面的峰值），最后得到的 result 就是 2（峰值个数为 2 即摆动序列长度为 2）

经过以上分析后，我们可以写出如下代码：

// 版本一
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if (nums.size() <= 1) return nums.size();
        int curDiff = 0; // 当前一对差值
        int preDiff = 0; // 前一对差值
        int result = 1;  // 记录峰值个数，序列默认序列最右边有一个峰值
        for (int i = 0; i < nums.size() - 1; i++) {
            curDiff = nums[i + 1] - nums[i];
            // 出现峰值
            if ((preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)) {
                result++;
            }
            preDiff = curDiff;
        }
        return result;
    }
};

时间复杂度：O(n)
空间复杂度：O(1)

此时大家是不是发现以上代码提交也不能通过本题？

所以此时我们要讨论情况三！

情况三：单调坡度有平坡

在版本一中，我们忽略了一种情况，即如果在一个单调坡度上有平坡，例如[1,2,2,2,3,4]，如图：

图中，我们可以看出，版本一的代码在三个地方记录峰值，但其实结果因为是 2，因为单调中的平坡不能算峰值（即摆动）。

之所以版本一会出问题，是因为我们实时更新了 prediff。

那么我们应该什么时候更新 prediff 呢？

我们只需要在这个坡度摆动变化的时候，更新 prediff 就行，这样 prediff 在单调区间有平坡的时候就不会发生变化，造成我们的误判。

所以本题的最终代码为：

// 版本二
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if (nums.size() <= 1) return nums.size();
        int curDiff = 0; // 当前一对差值
        int preDiff = 0; // 前一对差值
        int result = 1;  // 记录峰值个数，序列默认序列最右边有一个峰值
        for (int i = 0; i < nums.size() - 1; i++) {
            curDiff = nums[i + 1] - nums[i];
            // 出现峰值
            if ((preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)) {
                result++;
                preDiff = curDiff; // 注意这里，只在摆动变化的时候更新prediff
            }
        }
        return result;
    }
};

其实本题看起来好像简单，但需要考虑的情况还是很复杂的，而且很难一次性想到位。

本题异常情况的本质，就是要考虑平坡，平坡分两种，一个是上下中间有平坡，一个是单调有平坡，如图：

代码实现

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length <= 1) {
            return nums.length;
        }
        //当前差值
        int curDiff = 0;
        //上一个差值
        int preDiff = 0;
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            //得到当前差值
            curDiff = nums[i] - nums[i - 1];
            //如果当前差值和上一个差值为一正一负
            //等于0的情况表示初始时的preDiff
            if ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)) {
                count++;
                preDiff = curDiff;
            }
        }
        return count;
    }
}

思路 2（动态规划）

感觉没怎么看明白

考虑用动态规划的思想来解决这个问题。

很容易可以发现，对于我们当前考虑的这个数，要么是作为山峰（即 nums[i] > nums[i-1]），要么是作为山谷（即 nums[i] < nums[i - 1]）。

设 dp 状态dp[i][0]，表示考虑前 i 个数，第 i 个数作为山峰的摆动子序列的最长长度
设 dp 状态dp[i][1]，表示考虑前 i 个数，第 i 个数作为山谷的摆动子序列的最长长度

则转移方程为：

dp[i][0] = max(dp[i][0], dp[j][1] + 1)，其中0 < j < i且nums[j] < nums[i]，表示将 nums[i]接到前面某个山谷后面，作为山峰。
dp[i][1] = max(dp[i][1], dp[j][0] + 1)，其中0 < j < i且nums[j] > nums[i]，表示将 nums[i]接到前面某个山峰后面，作为山谷。

初始状态：

由于一个数可以接到前面的某个数后面，也可以以自身为子序列的起点，所以初始状态为：dp[0][0] = dp[0][1] = 1。

C++代码如下：

class Solution {
public:
    int dp[1005][2];
    int wiggleMaxLength(vector<int>& nums) {
        memset(dp, 0, sizeof dp);
        dp[0][0] = dp[0][1] = 1;
        for (int i = 1; i < nums.size(); ++i) {
            dp[i][0] = dp[i][1] = 1;
            for (int j = 0; j < i; ++j) {
                if (nums[j] > nums[i]) dp[i][1] = max(dp[i][1], dp[j][0] + 1);
            }
            for (int j = 0; j < i; ++j) {
                if (nums[j] < nums[i]) dp[i][0] = max(dp[i][0], dp[j][1] + 1);
            }
        }
        return max(dp[nums.size() - 1][0], dp[nums.size() - 1][1]);
    }
};

时间复杂度：O(n^2)
空间复杂度：O(n)

进阶

可以用两棵线段树来维护区间的最大值

每次更新dp[i][0]，则在tree1的nums[i]位置值更新为dp[i][0]
每次更新dp[i][1]，则在tree2的nums[i]位置值更新为dp[i][1]
则 dp 转移方程中就没有必要 j 从 0 遍历到 i-1，可以直接在线段树中查询指定区间的值即可。

时间复杂度：O(nlog n)
空间复杂度：O(n)

代码实现

// DP
class Solution {
    public int wiggleMaxLength(int[] nums) {
        // 0 i 作为波峰的最大长度
        // 1 i 作为波谷的最大长度
        int dp[][] = new int[nums.length][2];

        dp[0][0] = dp[0][1] = 1;
        for (int i = 1; i < nums.length; i++){
            //i 自己可以成为波峰或者波谷
            dp[i][0] = dp[i][1] = 1;

            for (int j = 0; j < i; j++){
                if (nums[j] > nums[i]){
                    // i 是波谷
                    dp[i][1] = Math.max(dp[i][1], dp[j][0] + 1);
                }
                if (nums[j] < nums[i]){
                    // i 是波峰
                    dp[i][0] = Math.max(dp[i][0], dp[j][1] + 1);
                }
            }
        }

        return Math.max(dp[nums.length - 1][0], dp[nums.length - 1][1]);
    }
}

53. 最大子序和※

建议：

题目链接： https://leetcode.cn/problems/maximum-subarray/
文章讲解： https://programmercarl.com/0053.%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C.html
视频讲解：

题目分析

方案一：贪心算法

此题想出来程序在那里贪的心不是一件容易的事情。

其根据计算数值的和来进行贪心计算，当sum<0的时候，相加只会意味着拉低后面的和值，所以直接舍弃前面已经相加的数据，从下一个坐标重新开始相加。在相加的过程中，更新最终的结果。

class Solution {
    public int maxSubArray(int[] nums) {
        // 贪心算法
        int result = Integer.MIN_VALUE,
                sum = 0;

        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (sum > result) result = sum;

            if (sum < 0) sum = 0;
        }
        return result;
    }
}

结果

解答成功:
执行耗时:1 ms,击败了100.00% 的Java用户
内存消耗:56.4 MB,击败了32.03% 的Java用户

分析

时间复杂度：
O( n )

空间复杂度：
O( 1 )

方案二：动态规划

class Solution {
    public int maxSubArray(int[] nums) {
        // DP
        int result = nums[0];
        int[] dp = new int[nums.length];
        dp[0] = nums[0];

        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
            if (dp[i] > result) result = dp[i];
        }
        return result;

    }
}

结果

解答成功:
执行耗时:2 ms,击败了44.11% 的Java用户
内存消耗:56.2 MB,击败了43.11% 的Java用户

分析

时间复杂度：
O( n )

空间复杂度：
O( n )

代码随想录

https://programmercarl.com/0053.%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C.html

暴力解法

暴力解法的思路，第一层 for 就是设置起始位置，第二层 for 循环遍历数组寻找最大值

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int result = INT32_MIN;
        int count = 0;
        for (int i = 0; i < nums.size(); i++) { // 设置起始位置
            count = 0;
            for (int j = i; j < nums.size(); j++) { // 每次从起始位置i开始遍历寻找最大值
                count += nums[j];
                result = count > result ? count : result;
            }
        }
        return result;
    }
};

时间复杂度：O(n^2)
空间复杂度：O(1)

以上暴力的解法 C++勉强可以过，其他语言就不确定了。

贪心解法

贪心贪的是哪里呢？

如果 -2 1 在一起，计算起点的时候，一定是从 1 开始计算，因为负数只会拉低总和，这就是贪心贪的地方！

局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。

全局最优：选取最大“连续和”

局部最优的情况下，并记录最大的“连续和”，可以推出全局最优。

从代码角度上来讲：遍历 nums，从头开始用 count 累积，如果 count 一旦加上 nums[i]变为负数，那么就应该从 nums[i+1]开始从 0 累积 count 了，因为已经变为负数的 count，只会拖累总和。

这相当于是暴力解法中的不断调整最大子序和区间的起始位置。

那有同学问了，区间终止位置不用调整么？如何才能得到最大“连续和”呢？

区间的终止位置，其实就是如果 count 取到最大值了，及时记录下来了。例如如下代码：

1	`if (count > result) result = count;`

这样相当于是用 result 记录最大子序和区间和（变相的算是调整了终止位置）。

如动画所示：

红色的起始位置就是贪心每次取 count 为正数的时候，开始一个区间的统计。

那么不难写出如下 C++代码（关键地方已经注释）

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;
    }
};

时间复杂度：O(n)
空间复杂度：O(1)

当然题目没有说如果数组为空，应该返回什么，所以数组为空的话返回啥都可以了。

代码实现

class Solution {
    public int maxSubArray(int[] nums) {
        if (nums.length == 1){
            return nums[0];
        }
        int sum = Integer.MIN_VALUE;
        int count = 0;
        for (int i = 0; i < nums.length; i++){
            count += nums[i];
            sum = Math.max(sum, count); // 取区间累计的最大值（相当于不断确定最大子序终止位置）
            if (count <= 0){
                count = 0; // 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
            }
        }
       return sum;
    }
}

常见误区

误区一：

不少同学认为如果输入用例都是-1，或者都是负数，这个贪心算法跑出来的结果是 0，这是又一次证明脑洞模拟不靠谱的经典案例，建议大家把代码运行一下试一试，就知道了，也会理解为什么 result 要初始化为最小负数了。

误区二：

大家在使用贪心算法求解本题，经常陷入的误区，就是分不清，是遇到负数就选择起始位置，还是连续和为负选择起始位置。

在动画演示用，大家可以发现， 4，遇到 -1 的时候，我们依然累加了，为什么呢？

因为和为 3，只要连续和还是正数就会对后面的元素起到增大总和的作用。所以只要连续和为正数我们就保留。

这里也会有录友疑惑，那 4 + -1 之后不就变小了吗？会不会错过 4 成为最大连续和的可能性？

其实并不会，因为还有一个变量 result 一直在更新最大的连续和，只要有更大的连续和出现，result 就更新了，那么 result 已经把 4 更新了，后面连续和变成 3，也不会对最后结果有影响。

动态规划

当然本题还可以用动态规划来做

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        vector<int> dp(nums.size(), 0); // dp[i]表示包括i之前的最大连续子序列和
        dp[0] = nums[0];
        int result = dp[0];
        for (int i = 1; i < nums.size(); i++) {
            dp[i] = max(dp[i - 1] + nums[i], nums[i]); // 状态转移公式
            if (dp[i] > result) result = dp[i]; // result 保存dp[i]的最大值
        }
        return result;
    }
};

时间复杂度：O(n)
空间复杂度：O(n)

代码实现

// DP 方法
class Solution {
    public int maxSubArray(int[] nums) {
        int ans = Integer.MIN_VALUE;
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        ans = dp[0];

        for (int i = 1; i < nums.length; i++){
            dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
            ans = Math.max(dp[i], ans);
        }

        return ans;
    }
}

02_1_代码随想录算法训练营18期

#LeetCode #算法训练营

27、第八章贪心算法 part01

http://yuanql.top/2023/08/11/02_1_代码随想录算法训练营18期/27、第八章贪心算法 part01/

作者

Qingli Yuan

发布于

2023年8月11日

许可协议

2023年8月11日每日一题--1572. 矩阵对角线元素的和上一篇

2023年8月10日每日一题--1289. 下降路径最小和 II 下一篇

27、第八章 贪心算法 part01

本节内容

理论基础※

什么是贪心

贪心的套路（什么时候用贪心）

贪心一般解题步骤

455.分发饼干※

题目分析

方案一

结果

分析

方案二

结果

分析

代码随想录

思路

注意事项

其他思路

代码实现

376. 摆动序列※

题目分析

方案一

结果

分析

代码随想录

思路 1（贪心解法）

情况一：上下坡中有平坡

情况二：数组首尾两端

情况三：单调坡度有平坡

代码实现

思路 2（动态规划）

代码实现

53. 最大子序和※

题目分析

方案一：贪心算法

结果

分析

方案二：动态规划

结果

分析

代码随想录

暴力解法

贪心解法

代码实现

常见误区

动态规划

代码实现

27、第八章贪心算法 part01