# Maximize Sum Of Array After K Negations

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 = 1

**Output:** 5

**Explanation:** Choose index 1 and nums becomes [4,-2,3].

**Example 2:**

**Input:** nums = [3,-1,0,2], k = 3

**Output:** 6

**Explanation:** Choose indices (1, 2, 2) and nums becomes [3,1,0,2].

**Example 3:**

**Input:** nums = [2,-3,-1,5,-4], k = 2

**Output:** 13

**Explanation:** 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)