代码随想录算法训练营 Day28 贪心Ⅱ 股票交易 跳跃游戏 K取反

贪心

题目

122. 买卖股票的最佳时机 II - 力扣（LeetCode）
类似于上一道题目摆动序列，每天差值计算出来，总利润只要当前总和大于 0 的，否则不如卖出
列出每天的利润，只收集正利润

int maxProfit(vector<int>& prices) {int sum = 0;for (int i = 0; i < prices.size()-1; ++i) {sum += std::max(prices[i+1] - prices[i], 0);}return sum;
}

55. 跳跃游戏 - 力扣（LeetCode）
控制覆盖范围，局部最优是尽可能取覆盖范围，全局最优得到覆盖范围即可

bool canJump(vector<int>& nums) {// 特殊判断if (nums.size() == 0) return true;int cover = 0;for (int i = 0; i <= cover; ++i) {// 取最大可到达范围cover = std::max(i + nums[i], cover);if (cover >= nums.size()-1) return true;}return false;
}

45. 跳跃游戏 II - 力扣（LeetCode）
看覆盖范围能否覆盖

int jump(vector<int>& nums) {// 终止调节if (nums.size() == 1) return 0;// 中间变量int res = 0;int curCover = 0;int nextCover = 0;for (int i = 0; i < nums.size(); ++i) {// 时刻保持最大覆盖范围nextCover = std::max(i + nums[i], nextCover);// 到达当前范围结尾if (i == curCover) {curCover = nextCover;res++;// 最大范围达到即退出if (nextCover >= nums.size() - 1) break;}}return res;
}

1005. K 次取反后最大化的数组和 - 力扣（LeetCode）
两次贪心思路，找绝对值最大的负数取反，取最小数进行取反将影响降到最低

static bool Cmp(int a, int b) {return abs(a) > abs(b);}int largestSumAfterKNegations(vector<int>& nums, int k) {std::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 sum = 0;for (int i = 0; i < nums.size(); ++i) sum += nums[i];return sum;
}