第一天没有利润，至少要第二天才会有利润，所以利润的序列比股票序列少一天！

从图中可以发现，其实我们需要收集每天的正利润就可以，收集正利润的区间，就是股票买卖的区间，而我们只需要关注最终利润，不需要记录区间。那么只收集正利润就是贪心所贪的地方！

局部最优：收集每天的正利润，全局最优：求得最大利润。

class Solution {
public:int maxProfit(vector<int>& prices) {int ans = 0, cur = INT32_MAX;for(int i = 0; i < prices.size(); i++){if(prices[i] < cur) cur = prices[i];else {ans = ans + (prices[i] - cur);cur = prices[i];}}return ans;}
};

class Solution {
public:bool canJump(vector<int>& nums) {int max_cover = 0;for(int i = 0; i <= max_cover; i++){max_cover = max(max_cover, i + nums[i]); //注意这里是nums[i] + i!!!!!!if(max_cover >= nums.size() - 1) return true;}return false;}
};

class Solution {
public:int jump(vector<int>& nums) {if(nums.size() <= 1) return 0;int ans = 0, next_cover = 0, cur_cover = nums[0];for(int i = 0; i < nums.size(); i++){next_cover = max(next_cover, i + nums[i]);if (cur_cover >= nums.size() - 1) return ans + 1; //相当于剪枝，该判断不能嵌套到下面if语句中！！！！！！if(cur_cover == i) {cur_cover = next_cover;ans = ans + 1;}}return -1;}
};

class Solution { //版本一 条件判断比较复杂
public:int largestSumAfterKNegations(vector<int>& nums, int k) {int ans = 0, index;// 第一步 从小到大排序sort(nums.begin(), nums.end());// 第二步 从小到大反转负数，nums[index] < 0要放后面for(index = 0; k > 0 && index < nums.size() && nums[index] < 0; index++){nums[index] = -nums[index]; k--;}// 第三步 反转绝对值最小的正数if(k % 2 == 1) {if((index> 0 && index < nums.size() && nums[index] > nums[index - 1]) || index == nums.size()) index = index - 1;nums[index] = -nums[index];}// 第四步 求和返回for(int num : nums) ans += num;return ans;}
};

class Solution { // 版本二 注意仿函数写法，必须用static修饰static bool cmp(int a, int b) { // 注意仿函数的写法！！！！！！return abs(a) > abs(b);
}
public:int largestSumAfterKNegations(vector<int>& A, int K) {int res = 0;// 第一步 将数组按照绝对值大小从大到小排序sort(A.begin(), A.end(), cmp);// 第二步 从前向后遍历，遇到负数将其变为正数for (int i = 0; K > 0 && i < A.size(); i++) {if(A[i] < 0) {A[i] = -A[i]; K--;}}// 第三步 若K还大于0，那么反复转变数值最小的元素if (K % 2 == 1) A[A.size() - 1] *= -1;// 第四步 求和返回for (int a : A) res += a;return res;}
};