贪心算法 - 阿晶

贪心算法（greedy algorithm）是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。贪心算法只关注当前所知，不分析历史。最小生成树、哈夫曼编码等都可以用贪心算法解决。无法解决所有最优化问题。»

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

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

1
2
3
4
5
6
7
8


输入: [7,1,5,3,6,4]
输出: 7

输入: [7,6,4,3,1]
输出: 0

输入: [1,2,3,4,5]
输出: 4

局部最优：预好就收

给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

1
2
3
4
5


输入: [2,3,1,1,4]
输出: true

输入: [3,2,1,0,4]
输出: false

局部最优：每一个位置可达到的最远 = max（之前位置可达到的最远, 每一个位置+该位置获得的跳数）

Table of Contents