Maximize Sum of Array after K Negations Leetcode Solution

Difficulty Level Easy
Frequently asked in Amazon
algorithms Array coding Interview interviewprep LeetCode LeetCodeSolutionsViews 2726

This post is on Maximize Sum Of Array After K Negations Leetcode Solution

Problem statement

In the problem ” Maximize Sum Of Array After K Negations” we are given an array arr and a value K. The array consists of integer values. We can change the value of arr[i] to -arr[i] K times. We can repeat the value of i. Our task is to maximize the array sum by applying this method K times and return the total array sum after modification.

Example

arr = [2,-3,-1,5,-4], k=2
13

Explanation:

Maximize Sum Of Array After K Negations Leetcode Solution

In the given array when we will replace -3 to 3 and -4 to 4 then the total sum of the array becomes 13.

Approach

Our task is to maximize the array sum and array consist of both positive and negative elements so, we will follow these steps:

  1. First of all we will sort the array because we want to change the sign of the smallest value. This will be useful in maximizing the array sum.
  2.  Now we will change the sign of at most K negative numbers.
  3. Meanwhile we will also keep track of if zero is present in the array or not.
  4. Find the array sum.
  5. Our final answer will be array sum if:
    1. value of K becomes zero.
    2. Zero is present in the array. This way we will keep changing the sign of zero.
    3. Remaiing value of K after changing the sign of negative values is even. This way we will make a positive number to negative number and then will make it positive again.
  6. Here value of K is negative so we will change the sign of smallest positive number K times. This will make it negative. Now we will return the new array sum.

Code for Maximize Sum Of Array After K Negations Leetcode Solution

C++ code

#include <bits/stdc++.h> 
using namespace std; 
    int largestSumAfterKNegations(vector<int>& A, int K) {
        sort(A.begin(),A.end());
        int sum=0,neg=0,zero=0;
        for(int i=0;i<A.size();i++)
        {
            if(A[i]==0)
                zero=1;
            if(A[i]<0&&K>0)
            {  A[i]=-A[i];K--;}
            sum+=A[i];
        }
        if(zero||K==0||K%2==0)
         return sum;
        else
            return sum-2*(*min_element(A.begin(),A.end()));       
    }
int main() 
{ 
 vector<int> arr = {2,-3,-1,5,-4}; 
 int k=2;
 cout<<largestSumAfterKNegations(arr,k)<<endl; 
 return 0;
}
13

Java code

import java.util.Arrays; 
public class Tutorialcup {
    public static int largestSumAfterKNegations(int[] A, int K) {
        Arrays.sort(A);
        int sum=0,neg=0,zero=0;
        for(int i=0;i<A.length;i++)
        {
            if(A[i]==0)
                zero=1;
            if(A[i]<0&&K>0)
            {  A[i]=-A[i];K--;}
            sum+=A[i];
        }
        if(zero==1||K==0||K%2==0)
         return sum;
        else
            return sum-2*(Arrays.stream(A).min().getAsInt());      
    }
  public static void main(String[] args) {
    int [] arr = {2,-3,-1,5,-4}; 
    int k=2;
    int ans=  largestSumAfterKNegations(arr,k);
    System.out.println(ans);
  }
}
13

Complexity Analysis of Maximize Sum Of Array After K Negations Leetcode Solution

Time complexity

The time complexity of the above code is O(n) because we are traversing the given array only once.

Space complexity

The space complexity of the above code is O(1) because we are using only a variable to store answers.

References

Translate »