每日一题——1005. K 次取反后最大化的数组和

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

给你一个整数数组 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了