贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
基本思路
- 建立数学模型来描述问题；
- 把求解的问题分成若干个子问题；
- 对每一子问题求解，得到子问题的局部最优解；
- 把子问题的解局部最优解合成原来解问题的一个解。
一些典型例题
活动安排问题
设有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，则可以直接返回
if(i + nums[i] >= nums.size() - 1)
return true;
//能达到的最远距离大于max_loc，则更新max_loc
if(i + nums[i] > max_loc)
max_loc = i + nums[i];
if(max_loc == i)
return false;
}
return false;
}
};?53. 最大子序和
给定一个整数数组 nums?，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组?[4,-1,2,1] 的和最大，为?6 。
#include "bits/stdc++.h"
using namespace std;
class Solution {
public:
int maxSubArray_greedy(vector<int>& nums) {
int ans=0, max = -1000000;
for(int i = 0; i < nums.size(); i++){
if(ans <= 0){
ans = nums[i];
}
else
ans += nums[i];
max = max > ans ? max : ans;
}
return max;
}
};?ans表示以当前元素结尾的最大连续子段和，遍历数组时，实时更新维护最大值max，同时我们应该注意的是，若ans<0，则应该抛弃ans的累计值（ans<0的话，会导致后续计算出来的值肯定小于当前元素，应该抛弃），重新计数。