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)
