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 = 2
ater 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)