贪心算法:
贪心法又称贪心算法、贪婪算法,在对问题求解时,总是做出在当前看来最好的选择。
简单地说,问题能够分解成子问题来解决,子问题的最优解能递推到最终问题的最优解。这种子问题最优解称为最优子结构。
贪心算法与动态规划的不同在于它对每个子问题的解决方案做的选择不能回退。动态规划则会保存以前的运算结果,并根据以前的结果对当前进行选择,有回退功能。
一个例子说明贪心算法与动态规划的不同:
假如有面值20 10 5 1的四种纸币,那么要兑换36块钱,最少需要几张纸币?
36 -20 = 16
16 - 10 = 6
6 - 5 = 1
1 - 1 = 0
所以一共需要4张纸币,20 10 5 1,但是这道题如果零钱面值换成10 9 1 兑换金额是18就会出问题了。
18 - 10 =8
8 - 8 *1 = 0;
所以需要9张纸币,而不是正确的解法9 * 2,这是因为贪心算法只做最优解没有回退功能。
代码实现

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int sum = 0;
        for(int i = 1;i < prices.size();i++)
        {
            sum += (prices[i] - prices[i - 1] > 0) ? prices[i] - prices[i - 1] : 0;
        }
        
        return sum;
    }
};

运行结果:

Runtime: 4 ms, faster than 99.76% of C++ online submissions for Best Time to Buy and Sell Stock II.
Memory Usage: 13.3 MB, less than 100.00% of C++ online submissions for Best Time to Buy and Sell Stock II.