贪心法

贪心法是一种简单而常用的算法思想，通常用于求解最优化问题。

贪心法的基本思路是：先根据题目所给条件，选择一个局部最优解，然后再利用一些贪心的策略，不断地扩展这个局部最优解，最终得到全局最优解。

具体来说，贪心法通常包含两个部分：一是构造解的过程，二是验证解是否是最优的过程。在构造解的过程中，要根据问题的约束条件选择合适的贪心策略，不断扩展当前已选定的解。在验证解是否是最优的过程中，要用数学方法证明所得到的解是最优解。

需要注意的是，贪心法并不是适用于所有问题的，有些问题可能无法用贪心法求解，或者通过贪心法求解得到的答案并不是最优解。因此，选择贪心法求解问题时需要具备一定的问题分析能力和经验，确保算法的正确性和有效性。

贪心法常用正确性证明手段有：

• 微扰（邻项交换）：证明在任意局面下，对局部最优策略的微小变化都会造成整体结果变差。通常用“排序”为辅助。
• 决策包容性：证明在任意局面下，做出局部最优决策后，在问题状态空间中的可达集合包含了做出其他任何决策后的可大集合。即局部最优决策提供的可能性包含任意决策提供的可能性。
• 决策范围扩展：有时无法直接证明局部最优解的正确性，则需要多进行一步决策来对上一步决策进行验证。
• 反证法
• 数学归纳法

例题 AcWing 1055 股票买卖Ⅱ

Description

给定一个长度为 N 的数组，数组中的第 i 个数字表示一个给定股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

Input

第一行包含整数 N，表示数组长度。

第二行包含 N 个不大于 10000 的正整数，表示完整的数组。

Output

输出一个整数，表示最大利润。

Range

1≤N≤105

Sample Input

6

7 1 5 3 6 4

Sample Output

7

N = int(input())
stock = list(map(int, input().split()))

profit = 0
for i in range(1, N):
    profit += max(stock[i] - stock[i - 1], 0)
print(profit)

其他例题

AcWing 110 防晒
AcWing 111 畜栏预定
AcWing 112 雷达设备
AcWing 114 国王游戏
AcWing 115 给树染色