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

今天的LeetCode题目又是难度为简单的题LeetCode 1005.K 次取反后最大化的数组和，先来看题。

题目

给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：

选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
重复这个过程恰好 k 次。可以多次选择同一个下标 i 。

以这种方式修改数组后，返回数组可能的最大和。

题解

读起来非常拗口而且难以理解，还好LeetCode的题目都会给示例，我们来看看。

示例1：

输入：nums = [4,2,3], k = 1

输出：5

解释：选择下标 1 ，nums 变为 [4,-2,3] 。

示例2：

输入：nums = [2,-3,-1,5,-4], k = 2

输出：13

解释：选择下标 (1, 4) ，nums 变为 [2,3,-1,5,4] 。

看完以后，我终于理解了题目说的是啥意思，通俗的来说就是拿nums[i]进行k次的nums[i]*=-1，随后把nums里的元素加起来返回，而且要是最大值。

进行一波分析，从nums里拿出哪个元素进行变换，会使得最后的结果是最大呢，很显然是nums中最小的那个元素。

用示例2举个例子，nums=[2,3,-1,5,-4] ; k=2，我们将最小那个元素掏出，是nums[4]=-4,给它进行变换，得到nums[4]=4, 变化后的结果为nums=[2,3,1,5,4],完成了第一次转换，所以k–,k=1。再进行一次变换，掏出nums最小那个元素，为nums[2]=1, 给它进行变换，结果为nums=[2,3,-1,5,4],此时k=0，已经完成变换，返回最后nums中的元素的和，即为结果。

代码示例

//使用递归
class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        int n=0;
        for(int i=0;i<nums.size();i++)
            if(nums[n]>nums[i])
                n=i;
        k--;
        nums[n]*=-1;
        if(k<=0)
        {
            int ans=0;
            for(auto i:nums)
                ans+=i;
            return ans;
        }
        return largestSumAfterKNegations(nums,k);
    }
};

修改

经过大佬指点，对上述代码进行优化。

原代码使用了递归的办法进行了深度为k次的递归，然而这是没有必要的，仅仅需要一个for循环即可搞定。
算法也可以进行优化，我们可以将nums使用sort()进行升序排序，从低位开始往上将0到k-1的负数倒转，如果发现nums[i]是正数，就跳出循环。
跳出循环后如果k!=0,那么就再次进行sort()排序，然后nums[0]*=(-1)^k),最后再输出结果。

优化过后执行时间从30ms缩减至4ms

代码示例（改）

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end());
        for(int i=0;nums[i]<0&&i<nums.size()&&k!=0;i++)
            nums[i]*=-1,k--;
        if(k!=0)
        {
            sort(nums.begin(),nums.end());
            nums[0]*=pow(-1,k);
        }
        int ans=0;
        for(auto i:nums)
            ans+=i;
        return ans;
    }
};