Greedy Algorithms

Greedy Algorithms

A greedy algorithm always makes the choice that looks best at the current moment, rather than considering the overall optimum directly. It produces a locally optimal choice in some sense. Greedy algorithms do not find the global optimum for every problem; choosing the right greedy strategy is crucial.

There is no fixed framework for designing a greedy algorithm. The key is choosing the strategy. A greedy algorithm does not solve every problem optimally: its choices must have no aftereffect, meaning that later steps do not change earlier decisions and the next step depends on the current state.

Before using a greedy algorithm, determine whether the problem is suitable. Problems that admit a greedy solution generally have two properties:

1. Greedy choice: a globally optimal solution can be reached through a series of locally optimal choices. A choice may depend on earlier choices but does not need to depend on later ones.

2. Optimal substructure: an optimal solution to the problem contains optimal solutions to its subproblems.

The basic approach is:

1. Build a mathematical model of the problem.

2. Divide the problem into subproblems.

3. Find a locally optimal solution for each subproblem.

4. Combine these solutions into a solution to the original problem.

Best time to buy and sell stock

An array gives the price of one stock on each day. Design an algorithm to calculate the maximum profit. You may complete as many transactions as possible, but cannot participate in multiple transactions simultaneously: sell your previous holding before buying again.

Example

Input: [7, 1, 5, 3, 6, 4]

Output: 7

Explanation: buy on day 2 at 1 and sell on day 3 at 5, earning 5 − 1 = 4. Then buy on day 4 at 3 and sell on day 5 at 6, earning 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;
}