贪心算法

贪心算法（Greedy Algorithm）

贪心算法，又称贪婪算法，是指在对问题求解时，总是做出在当前看来是最好的选择，也就是说不从整体最优上加以考虑。算法得到的是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键在于贪心策略的选择。

贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。

在利用贪心算法求解问题之前，必须需要清楚什么样的问题适合用贪心算法。一般而言，能够利用贪心算法求解的问题都会具备以下两点性质：

1. 贪心选择：当某一个问题的整体最优解可通过一系列局部最优选择达到，并且每次做出的选择可以依赖以前做出的选择，但不需要依赖后面需要做出的选择。

2. 最优子结构：如果一个问题的最优解包含其子问题的最优解，则此问题具备最优子结构的性质。

贪心算法的基本思路分为：

1. 建立数学模型描述问题。

2. 把求解的问题分成若干个子问题。

3. 对每个子问题求解，得到子问题的局部最优解。

4. 把子问题的局部最优解合成为原问题的解。

买卖股票的最佳时期

给定一个数组，它的第i个元素是一支给定股票第i天的价格。设计一个算法来计算所能获取的最大利润。（提示：可以尽可能地完成更多的交易，但不能同时参与多笔交易，在再次购买前出售掉之前的股票）。

示例

输入：[7, 1, 5, 3, 6, 4]

输出：7

解释：在第2天（股票价格 = 1）的时候买入，在第3天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。随后，在第4天（股票价格 = 3）的时候买入，在第5天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3。

#include <stdio.h>

int max_profit(int *prices, int n) {
    int profit = 0;
    for (int i = 0; i < n - 1; i++) {
        if (prices[i] < prices[i + 1]) {
            profit += prices[i + 1] - prices[i];
        }
    }
    return profit;
}

int main(void) {
    int prices[] = {7, 1, 5, 3, 6, 4};
    int n = sizeof(prices) / sizeof(prices[0]);
    printf("%d\n", max_profit(prices, n));
    return 0;
}