一、LeetCode 122.买卖股票的最佳时机II
题目链接/文章讲解/视频讲解：https://programmercarl.com/0122.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BAII.html
状态：已解决
1.思路
这题的核心思路是：利润可分解，总利润最大可以分解为每天的利润最大（也就是丢弃负收益）。
此题不像上题求连续子序列的和，因为要连续，所以遇到负数也不一定要停，因为只要连续和还为正数，就对后面的总和有利。但此题可以离散，中途的负收益只会拉低我们的总收益，因此直接跳过，只加上正收益即可。
2.代码实现
class Solution {
public:
int maxProfit(vector<int>& prices) {
int result=0;
for(int i=1;i<prices.size();i++){
if(prices[i]-prices[i-1]>0)
result += prices[i]-prices[i-1];
}
return result;
}
};（ps: 这题也可以根据摆动序列的思路来做，也就是计算下坡的长度，但是较复杂，搞了二十分钟没搞出来（））
二、55. 跳跃游戏
题目链接/文章讲解/视频讲解：https://programmercarl.com/0055.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8F.html
状态：已解决
1.思路
这题其实已经很简化了，没有要求给出能够到达终点的最优路径，只要求给出是否能够到达终点。要求是否能够到达终点，其实也就是求是否最远跳跃点能否超过终点，也就是说，每个点都选择跳到这个点能够到达的最远处，然后看能够到达的范围是否覆盖了终点即可：
每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。
贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。如图：
2.代码实现
class Solution {
public:
bool canJump(vector<int>& nums) {
vector<int> area(nums.size(),0);
int cover = 0;
for(int i=0;i<=cover;i++){//注意是小于等于cover，因为只有一直在覆盖范围内逐渐向外延伸到达的终点才有效
//如果最远跳跃点超过了终点，但中途有个点没有在覆盖范围内，证明路是不通的，也到达不了终点
cover = max(cover,i+nums[i]);
if(cover >= nums.size()-1) return true;
}
return false;
}
};三、45.跳跃游戏II
题目链接/文章讲解/视频讲解：https://programmercarl.com/0045.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8FII.html
状态：已解决
1.思路
本题的思路其实和55题类似，也是要求覆盖范围，不同的是55题是根据覆盖范围判断是否能够到达终点，而本题是根据更新覆盖范围的次数来确定最小跳数。核心原理是：每一个最大覆盖范围其实就是某一个起点可以到达的地方，因此更新过多少次覆盖范围也就是更新过多少次起点，或者说是跳到过多少节点，最后覆盖到终点时的更新次数即为最小跳数。
这里需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。如果移动下标达到了当前这一步的最大覆盖最远距离了，还没有到终点的话，那么就必须再走一步来增加覆盖范围，直到覆盖范围覆盖了终点
从图中可以看出来，就是移动下标达到了当前覆盖的最远距离下标时，步数就要加一，来增加覆盖距离。最后的步数就是最少步数。
这里还是有个特殊情况需要考虑，当移动下标达到了当前覆盖的最远距离下标时
- 如果当前覆盖最远距离下标不是是集合终点，步数就加一，还需要继续走。
- 如果当前覆盖最远距离下标就是是集合终点，步数不用加一，因为不能再往后走了。
2.代码实现
class Solution {
public:
int jump(vector<int>& nums) {
if (nums.size() == 1) return 0;
int cover = 0;
int result = 0;
int maxCover=0;
for(int i=0;i<=cover;i++){
maxCover = max(maxCover,i+nums[i]);//记录最大覆盖范围，先不急着更新，先把当前覆盖范围算完。
if(i == cover){//先看当前覆盖范围内得到的新最大覆盖范围是否包含终点
result++;//无论这一跳是否达到终点，步数都要加1，因为当前还没跳出这一跳
cover=maxCover;//现在跳到下个点了
if(cover >= nums.size()-1) break;//此时能够到达终点，停止循环
}
}
return result;
}
};
