# Maximize Sum Of Array After K Negations

2 min readAug 27, 2021

--

Given an integer array `nums` and an integer `k`, modify the array in the following way:

• choose an index `i` and replace `nums[i]` with `-nums[i]`.

You should apply this process exactly `k` times. You may choose the same index `i` multiple times.

Return the largest possible sum of the array after modifying it in this way.

Example 1:

`Input: nums = [4,2,3], k = 1Output: 5Explanation: Choose index 1 and nums becomes [4,-2,3].`

Example 2:

`Input: nums = [3,-1,0,2], k = 3Output: 6Explanation: Choose indices (1, 2, 2) and nums becomes [3,1,0,2].`

Example 3:

`Input: nums = [2,-3,-1,5,-4], k = 2Output: 13Explanation: Choose indices (1, 4) and nums becomes [2,3,-1,5,4]`

Approach 1

Sort the array, then negate all k possible negative number .After negating the negative number, either k numbers are finished negating, in that case return the current sum of the array , or if still some more times of negation still remain, then sort the array again(this is because if a negative number has greater magnitude than other positive numbers in the array , then this could alter the order of sorted array ). Now the least element which is at the first index is negated multiple times , such that k negation are finished , for this mod%2 operation can be used since the cycle repeat for even number of times .

The solution is given below:

`def largestSumAfterKNegations(nums,k):        nums.sort()        i=0        while(True):            if(i>=len(nums) or  nums[i]>0 or k<=0):                break            if(nums[i]<0 and k>0):                nums[i]=-1*nums[i]                k-=1               i+=1        nums.sort()            if(k==0):            return sum(nums)        else:if(0 in nums):                return sum(nums)            else:                if(k%2!=0):                    nums[0]=nums[0]*-1                return sum(nums)`

Time complexity: 0(nlgln)

Space :0(1)

Approach 2:

At anytime we would mean to negate the least number currently in the list so that that maximizes the sum.

Take an example

`say, nums = [2,-3,-1,5,-4], k = 2ater step 1 negation    nums=[2,3,-1,5,-4]after second negation  nums=[2,3,-1,5,4]   sum is 2+3-1+5+4 =13 `

This idea essentially suggest the usage of min heap or priority queue .

Time complexity: 0(nlgln)

Space :0(1)