给你一个整数数组 nums 和一个整数 k ,按以下方法修改该数组:
选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
以这种方式修改数组后,返回数组 可能的最大和
public class Solution { public int LargestSumAfterKNegations(int[] nums, int k) { int max = 0; if(k!=0) { int minusIndex = 0; Array.Sort(nums); for(int i=0; i<nums.Length; i++) { if(nums[i] <= 0) { minusIndex++; } } if(k <= minusIndex) { for(int i=0;i<k;i++) { nums[i] = -nums[i]; } } else { for(int i=0; i<nums.Length; i++) { if(nums[i] < 0) { nums[i] = -nums[i]; } } Array.Sort(nums); if((k - minusIndex)%2 != 0) { nums[0] = -nums[0]; } } } for(int i=0; i<nums.Length; i++) { max += nums[i]; } return max; } }
不知道我这么写算不算空间换时间
总之人生第一次用时100%
说说我的思路吧
k=0的情况直接啥也不用做,输出数组元素的和就完事了
然后是k>0的情况
这里我引入一个计数的变量minusIndex
去计算数组里负数和0的数量
那么就会有两种情况
第一种情况:k小于或者等于minusIndex的数量
那么就升序排序后从头开始的k个元素取反
因为排序后被取反的最多就只能到0的位置
所以元素和一定是最大值
第二种情况:k大于minusIndex的数量
那么所有的负数元素都得取反了
关键在取反后,多的k – minusIndex取反次数要如何处理
这里同样只会有两种情况
- 一种是偶数,因为可以在同一元素取反,所以相当于没取反
- 一种是奇数,一定要有一个值取反
如果大家的绝对值都不等于0那就是取最小值
如果有0的话那不用说就肯定取0了
所以我们在这里再进行一次排序
然后判断多了几次,偶数次啥也不用干,奇数次无脑取反第0个元素就ok了