Blogs Hub

by Sumit Chourasia | Oct 05, 2020 | Category :coding | Tags : algorithm data-structure easy greedy leetcode min-heap

Maximize Sum Of Array After K Negations - Greedy - Easy - LeetCode

Maximize Sum Of Array After K Negations - Greedy - Easy - LeetCode

Given an array A of integers, we must modify the array in the following way: we choose an i and replace A[i] with -A[i], and we repeat this process K times in total.  (We 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: A = [4,2,3], K = 1
Output: 5
Explanation: Choose indices (1,) and A becomes [4,-2,3].
Example 2:

Input: A = [3,-1,0,2], K = 3
Output: 6
Explanation: Choose indices (1, 2, 2) and A becomes [3,1,0,2].
Example 3:

Input: A = [2,-3,-1,5,-4], K = 2
Output: 13
Explanation: Choose indices (1, 4) and A becomes [2,3,-1,5,4].
 

Note:

1 <= A.length <= 10000
1 <= K <= 10000
-100 <= A[i] <= 100

public class Solution {
    int[] heap;
    int pos=1;
    public int LargestSumAfterKNegations(int[] A, int K) {
        heap = new int[A.Length+1];
        for(int i=0;i<A.Length;i++){
            Insert(A[i]);
        }
        
        for(int i=1;i<=K;i++){
            int min = ExtractMin();
            Insert(-1*min);            
        }
        
        int sum =0;
        while(pos>1){
            sum+=ExtractMin();
        }
        
        return sum;
    }
    
    private int ExtractMin(){
        int min = heap[1];
        pos--;
        heap[1]=heap[pos];
        HeapifyDown(1);
        return min;
    }
    
    private void HeapifyDown(int index){
        int left = 2*index;
        int right = left +1;
        if(left > pos){
            return;
        }
        if(right > pos){
            int temp = heap[left];
            heap[left]=heap[index];
            heap[index]=temp;
            HeapifyDown(left);
            return;
        }
        
        if(heap[left]<heap[right] && heap[left]<heap[index]){
            int temp = heap[left];
            heap[left]=heap[index];
            heap[index]=temp;
            HeapifyDown(left);
        }
        else if(heap[right]<heap[index]){
            int temp = heap[right];
            heap[right]=heap[index];
            heap[index]=temp;
            HeapifyDown(right);
        }
    }
    
    private void Insert(int val){
        heap[pos]=val;
        HeapifyUp(pos);
        pos++;
    }
    
    private void HeapifyUp(int index){
        int parent = index/2;
        if(parent<1){
            return;
        }
        if(heap[parent]>heap[index]){
            int temp = heap[parent];
            heap[parent]=heap[index];
            heap[index]=temp;
            HeapifyUp(parent);
        }
    }
}

Time Complexity: O(nlogn)

Space Complexity: O(logn)