Maximizar la suma de arreglos después de K negaciones | conjunto 2

Dada una array de tamaño n y un número k. Debemos modificar la array K número de veces. Aquí modificar array significa que en cada operación podemos reemplazar cualquier elemento de array arr[i] por -arr[i]. Necesitamos realizar esta operación de tal manera que después de K operaciones, la suma de la array debe ser máxima.

Ejemplos: 

Input : arr[] = {-2, 0, 5, -1, 2} 
        K = 4
Output: 10
// Replace (-2) by -(-2), array becomes {2, 0, 5, -1, 2}
// Replace (-1) by -(-1), array becomes {2, 0, 5, 1, 2}
// Replace (0) by -(0), array becomes {2, 0, 5, 1, 2}
// Replace (0) by -(0), array becomes {2, 0, 5, 1, 2}

Input : arr[] = {9, 8, 8, 5} 
        K = 3
Output: 20

Le recomendamos encarecidamente que haga clic aquí y lo practique antes de pasar a la solución.

Hemos discutido una solución O (nk) en la publicación a continuación.
Maximizar la suma de arreglos después de K negaciones | Conjunto 1
La idea utilizada en la publicación anterior es reemplazar el elemento mínimo arr[i] en la array por -arr[i] para la operación actual. De esta manera, podemos hacer la suma máxima de la array después de K operaciones. Una vez que el caso interesante es, una vez que el elemento mínimo se convierte en 0, no necesitamos hacer más cambios.
La implementación utilizada en la solución anterior utiliza la búsqueda lineal para encontrar el elemento mínimo. La complejidad de tiempo de la solución discutida anteriormente es O (nk)
En esta publicación, se implementa una solución optimizada que utiliza una cola de prioridad (o montón binario ) para encontrar el elemento mínimo rápidamente. 

A continuación se muestra la implementación de la idea. Utiliza la clase PriorityQueue en Java .

// A PriorityQueue based C++ program to
// maximize array sum after k negations.
#include <bits/stdc++.h>
using namespace std;
 
// Function to find Maximum sum
// after K negations
int MaxSum(int a[], int n, int k)
{
    int sum = 0;
     
    // Create a min heap for priority queue
    priority_queue<int, vector<int>, greater<int>> pq;
 
    // Insert all elements in f array in priority_queue
    for(int i = 0; i < n; i++)
    {
        pq.push(a[i]);
    }
 
    while (k--)
    {
         
        // Retrieve and remove min element
        int temp = pq.top();
 
        pq.pop();
         
        // Modify the minimum element and
        // add back to priority queue
        temp = (temp) * -1;
        pq.push(temp);
    }
     
    // Calculate the sum
    while (!pq.empty())
    {
        sum = sum + pq.top();
        pq.pop();
    }
    return sum;
}
 
// Driver Code
int main()
{
    int a[] = { -2, 0, 5, -1, 2 };
    int n = sizeof(a) / sizeof(a[0]);
    int k = 4;
 
    cout << MaxSum(a, n, k);
    return 0;
}
 
// This code is contributed by Harshit Srivastava

// A PriorityQueue based Java program to maximize array
// sum after k negations.
import java.util.*;
 
class maximizeSum
{
    public static int maxSum(int[] a, int k)
    {
        // Create a priority queue and insert all array elements
        // int
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int x : a)
            pq.add(x);
 
        // Do k negations by removing a minimum element k times
        while (k-- > 0)
        {
            // Retrieve and remove min element
            int temp = pq.poll();
 
            // Modify the minimum element and add back
            // to priority queue
            temp *= -1;
            pq.add(temp);
        }
 
        // Compute sum of all elements in priority queue.
        int sum = 0;
        for (int x : pq)
            sum += x;
        return sum;
    }
 
    // Driver code
    public static void main (String[] args)
    {
        int[] arr = {-2, 0, 5, -1, 2};
        int k = 4;
        System.out.println(maxSum(arr, k));
    }
}

Producción: 
 

10

Este artículo es una contribución de Prakhar . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.