贪心算法，又叫做贪婪算法。在对问题求解时， 总是做出在当前看来是最好的选择。然后通过局部的贪心来达到问题的全局最优解。
运用贪心策略解题，一般来说需要一步步的进行很多次的贪心选择。在经过一次贪心选择后,原问题将变成一个相似的,但规模更小的问题,而后的每一步都是当前看似最佳的选择,且每个选择都仅做一次。
贪心和动态规划的区别：
动态规划可以认为是含有重叠子问题的暴力算法,问题可以分解成多个子问题,子问题之间存在重叠,需要使用动态规划表格记录中间结果,本质还是要穷举所有解空间。
而贪心的精髓在于不用穷举所有解空间,就能找到答案。每一步都需要进行选择,选择需要满足贪心选择性质,问题具有最优子结构性质,子问题之间相互独立。
+++++++++++++++++++++++++++++++++++++华 丽 的 分 割 线+++++++++++++++++++++++++++++++++++++++
》〉》〉》〉》〉》〉》〉》〉》〉》〉》〉》〉最大子段和问题〈《〈《〈《〈《〈《〈《〈《〈《〈《〈《〈《
例题——最大子段和：
数组中子段的最大总和。例如, 123-543-6中的最大子段总和是1+2+3+ (-5) +4+3=8
【输入样例】
第一行中的整数n
第二行n整数
【输出样例】
整数
【数据范围】
1<= n<= 100000, -10000 <=序列元素 <= 10000
【方法1】前缀和
之前我们学过前缀和,一个子段的和能够表示成两个前缀和相减。即区间[Lr]的和为sum[r]-sum[l-1]。
要使差值最大， sum[r]固定，说明sum[l-1]尽可能小。
于是我们创建一个变量mn,表示前缀和的最小值。比较出最大的区间和。例如:序列{3, -5, 6, 4):
【方法2】贪心
找到以a[i-1]结尾的连续非空子段中和最大s[i-1]
如果这个子段s[i-1]为负数,那么以a1]结尾的连续非空子段中和最大的子段就是a[]本身;
如果这个子段s[i-1]为正数,那么以a1]结尾的连续非空子段中和最大的子段就是a[i]+s[i-1]。
在所有的s1中找最大的，例如：序列{3, -5, 6, 4}
+++++++++++++++++++++++++++++++++++++华 丽 的 分 割 线+++++++++++++++++++++++++++++++++++++++
》〉》〉》〉》〉》〉》〉》〉》〉》〉》〉》〉物品分配问题〈《〈《〈《〈《〈《〈《〈《〈《〈《〈《〈《〈
例题——分发蛋糕：
【题目描述】
假期将至,你是一位很有爱心的家长,想要在节假日的时候给你的孩子们一些小蛋糕。
但是,每个孩子最多只能给一块蛋糕。对每个孩子i,都有一个胃口值g[],这是能让孩子们满足胃口的蛋糕的最小尺寸;并且每块蛋糕j,都有一个尺寸s[]。如果s[]>=糕g[i],我们可以将这个蛋糕j分配给孩子i,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。
【输入样例】
第一行一个n和m,表示孩子数和蛋糕数接下来一行,输入n个孩子的胃口值g[i]。最后一行输入m个蛋糕的尺寸s[i]。
【输出样例】
能够满足的孩子数
【思路1】
从孩子胃口角度来看,胃口值最小的孩子最容易满足。
所以,应该按照胃口和尺寸从小到大排序,对于当前孩子,如果当前蛋糕满足不了他,就换下一个更大的蛋糕。
【思路2】
从蛋糕尺寸角度来看,大蛋糕更应该发给胃口大的人。
所以,应该按照胃口和尺寸从大到小排序,对于当前的大蛋糕,如果当前胃口大的孩子不够吃,就换下一个孩子来吃。
+++++++++++++++++++++++++++++++++++++华 丽 的 分 割 线+++++++++++++++++++++++++++++++++++++++
例题——分发糖果：
【题目描述】
老师想给孩子们分发糖果,有N个孩子站成了一条直线,老师会根据每个孩子的表现,预先给他们评分。
你需要按照以下要求,帮助老师给这些孩子分发糖果:
每个孩子至少分配到1个糖果。
相邻的孩子中，评分高的孩子必须获得更多的糖果。
那么这样下来,老师至少需要准备多少颗糖果呢?
【输入样例】
第一行一个n，表示孩子数。
接下来一行,输入n个孩子的评分。
【输出样例】
糖果数
思路：
这道题目可以用贪心算法求解。具体而言，我们可以将这个问题分解成两个子问题：
1.如何保证每个孩子至少分配到一个糖果?
2·如何保证相邻的孩子中,评分高的孩子必须获得更多的糖果?
1.如何保证每个孩子至少分配到一个糖果?
对于第一个子问题,我们发现每个孩子至少需要分配一个糖果,
因此我们可以将每个孩子的初始糖果数都初始化为 1。
2.如何保证相邻的孩子中，评分高的孩子必须获得更多的糖果？
如果同时关注一个人的左右两边并更改值的话，很容易影响前面已经确定的值，顾此失彼。
所以这道题目一定是要确定一边之后,再确定另一边。
例如七个孩子的评分依次为: 1225432
先从左到右,保证右边孩子的糖果数要么等于左边孩子的糖果数加1,要么不变;
再从右到左,保证左边孩子的糖果数要么等于右边孩子的糖果数加1,要么不变。
//从前向后
for( int i=1;i < ratings.size(); i++){ if (ratings [i]>ratings [i-1])
candyVec[i] = candyVec[i - 1] + 1;
}
//从后往前for( int i=1;i < ratings.size(); i++)
if(ratings[i]>ratings[i+1]) candyVec[i] = max(candyVec[i],candyVec[i + 1]+1);