121. 买卖股票的最佳时机

class Solution {public int maxProfit(int[] prices) {int ans = 0;int minPrice = prices[0];for(int p : prices){ans = Math.max(ans, p - minPrice);minPrice = Math.min(p, minPrice);}return ans;}
}

运用前缀和思想，

从左到右枚举卖出价格 prices[i]，那么要想获得最大利润，我们需要知道第 i 天之前，股票价格的最小值是什么，也就是从 prices[0] 到 prices[i−1] 的最小值，把它作为买入价格，这可以用一个变量 minPrice 维护。

请注意，minPrice 维护的是 prices[i] 左侧元素的最小值。

由于只能买卖一次，所以在遍历中，维护 prices[i]−minPrice 的最大值，就是答案。

from：灵茶山艾府

 122. 买卖股票的最佳时机 II

class Solution {public int maxProfit(int[] prices) {int res = 0;for(int i = 1; i < prices.length; i++){res += Math.max(prices[i] - prices[i - 1], 0);}return res;}
}

假如第 0 天买入，第 3 天卖出，那么利润为：prices[3] - prices[0]。

相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。

此时就是把利润分解为每天为单位的维度，而不是从 0 天到第 3 天整体去考虑！

55. 跳跃游戏

class Solution {public boolean canJump(int[] nums) {if(nums.length == 1) return true;int cover = 0;for(int i = 0; i <= cover; i++){cover = Math.max(i + nums[i], cover);if(cover >= nums.length - 1) return true;}return false;}
}

很清楚，good

45. 跳跃游戏 II

class Solution {public int jump(int[] nums) {int res = 0;int cur = 0;int next = 0;for(int i = 0; i <= cur && i < nums.length - 1; i++){next = Math.max(next, i + nums[i]);if(i == cur){res++;cur = next;}}return res;}
}

不好理解

灵神的和卡哥的合起来能看懂，有很多细节。

1005. K 次取反后最大化的数组和

class Solution {public int largestSumAfterKNegations(int[] nums, int k) {Arrays.sort(nums);for(int i = 0; i < nums.length && k > 0; i++){if(nums[i] < 0){nums[i] = -nums[i];k--;}}if(k % 2 == 1){Arrays.sort(nums);nums[0] = -nums[0];}int sum = 0;for(int num : nums){sum += num;}return sum;}
}

这题简单秒了