贪心算法总结_贪心算法的总结

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

目录

基本思路

一些典型例题

活动安排问题

55. 跳跃游戏

 53. 最大子序和

56. 合并区间

122. 买卖股票的最佳时机 II

53. 最大子数组和

基本思路

1. 建立数学模型来描述问题；
2. 把求解的问题分成若干个子问题；
3. 对每一子问题求解，得到子问题的局部最优解；
4. 把子问题的解局部最优解合成原来解问题的一个解。

一些典型例题

活动安排问题

设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si <fi 。要求设计程序，使得安排的活动最多。

 解题思路：题目的要求是安排的活动最多，故活动结束地早，那么安排的活动可以越多，对活动按照结束时间排序，然后遍历：若当前活动开始时间大于上一次活动的结束时间，则将其加入到队列中来。

55. 跳跃游戏

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int max_loc = 0;//最远可以到达的位置
        for(int i = 0; i < nums.size(); i++){
            //当前能达到的最远距离大于max_loc，则可以直接