【算法训练记录——Day32】

思路：贪心没理解，这个题毫无头绪。感觉就是求递增子序列是吧。
贪心需要把问题分解为若干个子问题的集合，子问题是什么呢？？？想不到，看题解
优秀，其实就是每天的正利润之和，把一段时间分解为若干天，只要为正就买入
第一天没有利润，利润的序列比股票序列少一天
知道了这层关系，那这道题就很简单了

贪心：int maxProfit(vector<int>& prices) {int max = 0;for(int i = 1; i < prices.size(); i++) {int lirun = prices[i] - prices[i-1];if(lirun > 0)max += lirun;}return max;}

思路二：动态规划
待补充

思路：直接就是忘了，看了一眼题解
怎么跳不重要，关键是覆盖范围，于是想到用一个变量记录当前能到达的最远点，遍历数组，更新最远点，最后只要最远点>size，那么就可以到达

	bool canJump(vector<int>& nums) {int maxSize = nums.size();int nowSize = 0;for(int i = 0; i < maxSize-1; i++) {// 如果当前范围不能再更新了，那就要退出// if(nowSize < i || nums[0] == 0) break;// 当前位置能到达的最远点如果小于等于当前位置，那就退出if(nowSize + nums[i] <= i) break;nowSize = max(nowSize, nums[i] + i);// 提前退出if(nowSize >= maxSize - 1) return true;}return nowSize >= maxSize-1;}

思路：

	int jump(vector<int>& nums) {if(nums.size() <= 1) return 0;int curDistance = 0; // 当前覆盖最远距离下标int nextDistance = 0; // 下一步覆盖的最远距离int res = 0;for(int i = 0; i < nums.size(); i++) {nextDistance = max(nums[i] + i, nextDistance);if(curDistance == i) {++res;curDistance = nextDistance;if(nextDistance >= nums.size() - 1) break;}}return res;}

	static bool cmp(int a, int b) {return abs(a) > abs(b);}
public:int largestSumAfterKNegations(vector<int>& nums, int k) {sort(nums.begin(), nums.end(), cmp);       // 第一步for (int i = 0; i < nums.size(); i++) { // 第二步if (nums[i] < 0 && k > 0) {nums[i] *= -1;k--;}}if (k % 2 == 1) nums[nums.size() - 1] *= -1; // 第三步int result = 0;for (int a : nums) result += a;        // 第四步return result;}