贪心---K 次取反后最大化的数组和 Posted on 2021-08-11 00:00:00 2021-08-11 00:00:00 by Author 摘要 给定一个数组，给定一个反转次数k,你可以对数组中的任意一个数或者多个数反转k次后，使得数组和的最大，你能办的到吗？？？？ # 贪心---K 次取反后最大化的数组和 1. 题目描述 - 给定一个整数数组 A，我们只能用以下方法修改该数组：我们选择某个索引 i 并将 A[i] 替换为 -A[i]，然后总共重复这个过程 K 次。（我们可以多次选择同一个索引 i。）以这种方式修改数组后，返回数组可能的最大和。 - **提示：** 1. `1 <= A.length <= 10000` 2. `1 <= K <= 10000` 3. `-100 <= A[i] <= 100` 2. 示例描述 - 示例一 ```java 输入：A = [4,2,3], K = 1 输出：5 解释：选择索引 (1,) ，然后 A 变为 [4,-2,3]。 ``` - 示例二 ```java 输入：A = [3,-1,0,2], K = 3 输出：6 解释：选择索引 (1, 2, 2) ，然后 A 变为 [3,1,0,2]。 ``` 3. 解题思路 - 本题是一道非常简单的题目，也许拿到题目想都不用想都能AC掉，但是这道题目中包含了贪心的思想。 - 首先这种思想体现在何处尼？我的理解是，首先如果数组元素都是正数，那么我们只用反转数组中最小的那个数k次即可，因为如果在反转其他的数，那么就会使得数组的总体和变小，不符合题意，此时就体现了贪心算法，局部最优解，从而使得全局最优。第二，如果数组中 有负数存在，那么把负数变成正数，那么就保证数组的和变得更大，从而局部最优，保证全局最优。 - 这是我个人的理解，具体算法思路在下面的代码中体现，每一步都有具体的解释与说明，也许下面的算法不是一个好的解法，但是贪心算法的思想在里面，大家可以自己体会以下。 4. 代码示例 ```java public int largestSumAfterKNegations(int[] nums, int k) { int result =0; //先对数组进行排序 Arrays.sort(nums); //如果数组的元素都大于零 //那么只用反转最小的一个数即可（不管k为多少，因为反转其他的数，会使总体的和变小） if(nums[0]>=0){ //如果K为奇数的话，就反转第一个数一次即可 //k为偶数，就不用反转了，因为k为偶数时，反转k次，该数又变回本来的值了，就没都必要了 if(k%2!=0) { nums[0] = -nums[0]; } //之后算出整个数组的和即可 for (int i = 0; i < nums.length; i++) { result+=nums[i]; } //返回最后的值 return result; } //如果数组中存在负数，那么需要把数组中的负数转化为正数，才能使得数组的和总体最大 for (int i= 0; i < nums.length ; i++) { //如果k为0的话，就不需要反转，直接退出循环，直接算和就好了。 if(k==0)break; //如果该元素为负数，并且k不为0，那么反转该元素 if(nums[i]<0&&k!=0){ //反转该元素 nums[i]=-nums[i]; //同时k的值减一 k--; continue; } //如果该元素为0，该元素之前的元素都已经反转为正数了，那么不管k为不为0，此时数组和已经最大了，直接让k=0,直接算数组的和了。 if(nums[i]==0&&k!=0){k=0;break;} //如果该元素已经大于0，并且k还不等于0， //那么回到算法开始的位置， // 对数组排序，找到数组中最小的一个元素，然后根据k的奇偶像，判断最小的元素是否需要反转。 if(nums[i]>0 && k!=0){ //数组排序 Arrays.sort(nums); //根据剩余k的个数，算最小的一个数是否需要反转 if(k%2!=0) { nums[0] = -nums[0]; //直接使k=0即可 k=0; //结束循环 break; } } } //如果整个数组都为负数，并且原始k值大于数组的长度 //那么对数组所有数都反转后，k还有剩余 //此时反转后数组的值都为正数，k不为0，那么又回到算法开始的位置 //对数组排序，找到数组中最小的一个元素，然后根据k的奇偶像，判断最小的元素是否需要反转。 if(k!=0){ Arrays.sort(nums); if(k%2!=0) { nums[0] = -nums[0]; } } result = 0; //计算数组的和 for (int i = 0; i < nums.length; i++) { result+=nums[i]; } //返回结果 return result; } ```
{{ item.content }}
{{ child.content }}