Last Updated on March 29, 2022 by Ria Pathak
CONCEPTS USED:
Greedy algorithm.
DIFFICULTY LEVEL:
Medium.
PROBLEM STATEMENT(SIMPLIFIED):
Tina knows PrepBuddy likes to play games with array elements. So she gave PrepBuddy an array A containing N integers. She wants to know the maximum possible sum of the array after performing the following operation M number of times:
- Choose an index i and flip the sign of the element present at that index, i.e replace A[i] with −A[i].
- It is allowed to choose the same index multiple times.
See original problem statement here
For Example :
2
5 4
-3 7 -1 -5 -3
4 3
-4 2 3 1
19
10
In the first test case choose index [0,2,3,4], so the array becomes [3,7,1,5,3] and the sum = 19.
In the second test case choose index [0,3,3], so the array becomes [4,2,3,1] and the sum = 10.OBSERVATION:
We need to flip the smallest number in each iteration!!
SOLVING APPROACH:
We need to flip the smallest number in each iteration.Why??
If the smallest number is negative ,flipping it would give us a positive number hence increasing our maximum sum.
If the smallest number is positive ,flipping it will reduce the sum but flipping any other number greater than it would lessen the sum even more.
Follow the algorithm:
Push all the given element in priority queue.
Now iterate till m and pop the top element of the queue ,flip it and push it back.
Remember to update the sum at each step.
Can you notice that we used greedy approach here??Remember what greedy says?
Always make the choice that seems to be the best at that moment. This means that make a locally-optimal choice in the hope that this choice will lead to a globally-optimal solution. That is what we did!
SOLUTIONS:
#include <stdio.h>
int tree_array_size ;
int heap_size = 0;
const int INF = 100000;
void swap( int *a, int *b ) {
int t;
t = *a;
*a = *b;
*b = t;
}
//function to get right child of a node of a tree
int get_right_child(int A[], int index) {
if((((2*index)+1) < tree_array_size) && (index >= 1))
return (2*index)+1;
return -1;
}
//function to get left child of a node of a tree
int get_left_child(int A[], int index) {
if(((2*index) < tree_array_size) && (index >= 1))
return 2*index;
return -1;
}
//function to get the parent of a node of a tree
int get_parent(int A[], int index) {
if ((index > 1) && (index < tree_array_size)) {
return index/2;
}
return -1;
}
void min_heapify(int A[], int index) {
int left_child_index = get_left_child(A, index);
int right_child_index = get_right_child(A, index);
// finding smallest among index, left child and right child
int smallest = index;
if ((left_child_index <= heap_size) && (left_child_index>0)) {
if (A[left_child_index] < A[smallest]) {
smallest = left_child_index;
}
}
if ((right_child_index <= heap_size && (right_child_index>0))) {
if (A[right_child_index] < A[smallest]) {
smallest = right_child_index;
}
}
// smallest is not the node, node is not a heap
if (smallest != index) {
swap(&A[index], &A[smallest]);
min_heapify(A, smallest);
}
}
void build_min_heap(int A[]) {
int i;
for(i=heap_size/2; i>=1; i--) {
min_heapify(A, i);
}
}
int minimum(int A[]) {
return A[1];
}
void extract_min(int A[]) {
int minm = A[1];
A[1] = A[heap_size];
heap_size--;
min_heapify(A, 1);
//return minm;
}
void decrease_key(int A[], int index, int key) {
A[index] = key;
while((index>1) && (A[get_parent(A, index)] > A[index])) {
swap(&A[index], &A[get_parent(A, index)]);
index = get_parent(A, index);
}
}
void increase_key(int A[], int index, int key) {
A[index] = key;
min_heapify(A, index);
}
void insert(int A[], int key) {
heap_size++;
A[heap_size] = INF;
decrease_key(A, heap_size, key);
}
void print_heap(int A[]) {
int i;
for(i=1; i<=heap_size; i++) {
printf("%d\n",A[i]);
}
printf("\n");
}
int main() {
int t;
scanf("%d",&t);{
int n,m;
scanf("%d%d",&n,&m);
tree_array_size=n;
int A[n];int sum=0;
for(int i=0;i<n;i++)
{
int x;
scanf("%d",&x);
sum+=x;
insert(A,x);
}
while(m--){
sum-=minimum(A);
int aux=-1*minimum(A);
extract_min(A);
sum+=aux;
insert(A,aux);
}
printf("%d",sum);
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
long long largestSumAfterKNegations(vector<int> &A, int K)
{
priority_queue<int, vector<int>, greater<>> q;
long long sum = 0;
for (auto w : A)
{
q.push(w);
sum += w;
}
while (K--)
{
sum -= q.top();
long long aux = -1 * q.top();
q.pop();
sum += aux;
q.push(aux);
}
return sum;
}
int main()
{
int t;
cin >> t;
while (t--)
{
int n, k;
cin >> n >> k;
vector<int> arr;
int ele;
for (int i = 0; i < n; i++)
{
cin >> ele;
arr.emplace_back(ele);
}
cout << largestSumAfterKNegations(arr, k) << "\n";
}
return 0;
}
import java.util.*;
import java.io.*;
import java.util.PriorityQueue;
class King
{
static int MaxSum(int arr[], int n,int m)
{
int i, sum = 0;
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (i = 0; i < n; i++)
{ pq.add(arr[i]);
sum+=arr[i];
}
while (m-->0)
{ int min = pq.poll();
sum -=min;
int aux = -1 * min;
sum += aux;
pq.add(aux);
}
return sum;
}
public static void main(String[] args)
{ Scanner sc = new Scanner(System.in);
int t= sc.nextInt();
while(t-- >0 ){
int n = sc.nextInt();
int m = sc.nextInt();
int arr[]=new int[n];
for(int i=0;i<n;i++)
{
arr[i] = sc.nextInt();
}
System.out.println(MaxSum(arr, n,m)); }
}
}
from queue import PriorityQueue def largestSumAfterKNegations(A, K): q = PriorityQueue() sum = 0 for w in A: q.put(w) sum += w while K: K -= 1 x = q.get() sum -= x aux = -1 * x sum += aux q.put(aux) return sum for _ in range(int(input())): n, k =map(int,input().split()) arr = list(map(int,input().split())) print(largestSumAfterKNegations(arr, k)) # your code goes here
[forminator_quiz id="1456"]
This article tried to discuss the concept of Greedy Algorithm. Hope this blog helps you understand and solve the problem. To practice more problems on greedy algorithm you can check out MYCODE | Competitive Programming