Suma de array máxima que se puede obtener después de exactamente k cambios

Dada una array arr[] de n enteros y un entero k . La tarea es maximizar la suma de la array después de realizar la operación dada exactamente k veces. En una sola operación, cualquier elemento de la array se puede multiplicar por -1 , es decir, se puede cambiar el signo del elemento.

Ejemplos: 

Entrada: arr[] = {-5, 4, 1, 3, 2}, k = 4 
Salida: 13 
Cambie el signo de -5 una vez y luego cambie el signo de 1 tres veces. 
Por lo tanto, cambia a -1 y la suma será 5 + 4 + (-1) + 3 + 2 = 13.
Entrada: arr[] = {-1, -1, 1}, k = 1 
Salida: 1  

Enfoque: si el recuento de elementos negativos en la array es count ,  

  1. Si count ≥ k entonces el signo de exactamente k números negativos cambiará comenzando desde el más pequeño.
  2. Si cuenta < k , cambia el signo de todos los elementos negativos a positivo y para las operaciones restantes, es decir, rem = k – cuenta
    • Si rem % 2 = 0 , no se realizarán cambios en la array actual, ya que cambiar el signo de un elemento dos veces da el número original.
    • Si rem % 2 = 1 , cambie el signo del elemento más pequeño de la array actualizada.
  3. Finalmente, imprima la suma de los elementos de la array actualizada.

A continuación se muestra la implementación del enfoque anterior: 

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Utility function to return the sum
// of the array elements
int sumArr(int arr[], int n)
{
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += arr[i];
 
    return sum;
}
 
// Function to return the maximized sum
// of the array after performing
// the given operation exactly k times
int maxSum(int arr[], int n, int k)
{
    // Sort the array elements
    sort(arr, arr + n);
 
    int i = 0;
    // Change signs of the negative elements
    // starting from the smallest
    while (i < n && k > 0 && arr[i] < 0) {
        arr[i] *= -1;
        k--;
        i++;
    }
 
    // If a single operation has to be
    // performed then it must be performed
    // on the smallest positive element
    if (k % 2 == 1) {
 
        // To store the index of the
        // minimum element
        int min = 0;
        for (i = 1; i < n; i++)
 
            // Update the minimum index
            if (arr[min] > arr[i])
                min = i;
 
        // Perform remaining operation
        // on the smallest element
        arr[min] *= -1;
    }
 
    // Return the sum of the updated array
    return sumArr(arr, n);
}
 
// Driver code
int main()
{
    int arr[] = { -5, 4, 1, 3, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 4;
 
    cout << maxSum(arr, n, k) << endl;
 
    return 0;
}

Java

// Java implementation of the above approach
import java.util.Arrays;
 
class GFG
{
 
// Utility function to return the sum
// of the array elements
static int sumArr(int arr[], int n)
{
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += arr[i];
 
    return sum;
}
 
// Function to return the maximized sum
// of the array after performing
// the given operation exactly k times
static int maxSum(int arr[], int n, int k)
{
    // Sort the array elements
    Arrays.sort(arr);
 
    int i = 0;
     
    // Change signs of the negative elements
    // starting from the smallest
    while (i < n && k > 0 && arr[i] < 0)
    {
        arr[i] *= -1;
        k--;
        i++;
    }
 
    // If a single operation has to be
    // performed then it must be performed
    // on the smallest positive element
    if (k % 2 == 1)
    {
 
        // To store the index of the
        // minimum element
        int min = 0;
        for (i = 1; i < n; i++)
 
            // Update the minimum index
            if (arr[min] > arr[i])
                min = i;
 
        // Perform remaining operation
        // on the smallest element
        arr[min] *= -1;
    }
 
    // Return the sum of the updated array
    return sumArr(arr, n);
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { -5, 4, 1, 3, 2 };
    int n = arr.length;
    int k = 4;
 
    System.out.println(maxSum(arr, n, k));
}
}
 
/* This code contributed by PrinciRaj1992 */

Python3

# Python 3 implementation of the approach
 
# Utility function to return the sum
# of the array elements
def sumArr(arr, n):
    sum = 0
    for i in range(n):
        sum += arr[i]
 
    return sum
 
# Function to return the maximized sum
# of the array after performing
# the given operation exactly k times
def maxSum(arr, n, k):
     
    # Sort the array elements
    arr.sort(reverse = False)
 
    i = 0
     
    # Change signs of the negative elements
    # starting from the smallest
    while (i < n and k > 0 and arr[i] < 0):
        arr[i] *= -1
        k -= 1
        i += 1
 
    # If a single operation has to be
    # performed then it must be performed
    # on the smallest positive element
    if (k % 2 == 1):
         
        # To store the index of the
        # minimum element
        min = 0
        for i in range(1, n):
             
            # Update the minimum index
            if (arr[min] > arr[i]):
                min = i
 
        # Perform remaining operation
        # on the smallest element
        arr[min] *= -1
 
    # Return the sum of the updated array
    return sumArr(arr, n)
 
# Driver code
if __name__ == '__main__':
    arr = [-5, 4, 1, 3, 2]
    n = len(arr)
    k = 4
 
    print(maxSum(arr, n, k))
 
# This code is contributed by
# Surendra_Gangwar

C#

// C# implementation of the above approach
using System;
using System.Linq;
 
class GFG
{
 
// Utility function to return the sum
// of the array elements
static int sumArr(int [] arr, int n)
{
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += arr[i];
 
    return sum;
}
 
// Function to return the maximized sum
// of the array after performing
// the given operation exactly k times
static int maxSum(int [] arr, int n, int k)
{
    // Sort the array elements
    Array.Sort(arr);
 
    int i = 0;
     
    // Change signs of the negative elements
    // starting from the smallest
    while (i < n && k > 0 && arr[i] < 0)
    {
        arr[i] *= -1;
        k--;
        i++;
    }
 
    // If a single operation has to be
    // performed then it must be performed
    // on the smallest positive element
    if (k % 2 == 1)
    {
 
        // To store the index of the
        // minimum element
        int min = 0;
        for (i = 1; i < n; i++)
 
            // Update the minimum index
            if (arr[min] > arr[i])
                min = i;
 
        // Perform remaining operation
        // on the smallest element
        arr[min] *= -1;
    }
 
    // Return the sum of the updated array
    return sumArr(arr, n);
}
 
// Driver code
static void Main()
{
    int []arr= { -5, 4, 1, 3, 2 };
    int n = arr.Length;
    int k = 4;
 
    Console.WriteLine(maxSum(arr, n, k));
}
}
 
// This code is contributed by mohit kumar 29

PHP

<?php
// PHP implementation of the approach
 
// Utility function to return the sum
// of the array elements
function sumArr($arr, $n)
{
    $sum = 0;
    for ($i = 0; $i < $n; $i++)
        $sum += $arr[$i];
 
    return $sum;
}
 
// Function to return the maximized sum
// of the array after performing
// the given operation exactly k times
function maxSum($arr, $n, $k)
{
    // Sort the array elements
    sort($arr);
 
    $i = 0;
    // Change signs of the negative elements
    // starting from the smallest
    while ($i < $n && $k > 0 &&
                $arr[$i] < 0)
    {
        $arr[$i] *= -1;
        $k--;
        $i++;
    }
 
    // If a single operation has to be
    // performed then it must be performed
    // on the smallest positive element
    if ($k % 2 == 1)
    {
 
        // To store the index of the
        // minimum element
        $min = 0;
        for ($i = 1; $i < $n; $i++)
 
            // Update the minimum index
            if ($arr[$min] > $arr[$i])
                $min = $i;
 
        // Perform remaining operation
        // on the smallest element
        $arr[$min] *= -1;
    }
 
    // Return the sum of the updated array
    return sumArr($arr, $n);
}
 
// Driver code
$arr = array( -5, 4, 1, 3, 2 );
$n = sizeof($arr);
$k = 4;
 
echo maxSum($arr, $n, $k), "\n";
 
// This code is contributed by ajit.
?>

Javascript

<script>
    // Javascript implementation of the above approach
     
    // Utility function to return the sum
    // of the array elements
    function sumArr(arr, n)
    {
        let sum = 0;
        for (let i = 0; i < n; i++)
            sum += arr[i];
 
        return sum;
    }
 
    // Function to return the maximized sum
    // of the array after performing
    // the given operation exactly k times
    function maxSum(arr, n, k)
    {
        // Sort the array elements
        arr.sort(function(a, b){return a - b});
 
        let i = 0;
 
        // Change signs of the negative elements
        // starting from the smallest
        while (i < n && k > 0 && arr[i] < 0)
        {
            arr[i] *= -1;
            k--;
            i++;
        }
 
        // If a single operation has to be
        // performed then it must be performed
        // on the smallest positive element
        if (k % 2 == 1)
        {
 
            // To store the index of the
            // minimum element
            let min = 0;
            for (i = 1; i < n; i++)
 
                // Update the minimum index
                if (arr[min] > arr[i])
                    min = i;
 
            // Perform remaining operation
            // on the smallest element
            arr[min] *= -1;
        }
 
        // Return the sum of the updated array
        return sumArr(arr, n);
    }
     
    let arr= [ -5, 4, 1, 3, 2 ];
    let n = arr.length;
    let k = 4;
   
    document.write(maxSum(arr, n, k));
 
</script>
Producción: 

13

 

Complejidad de tiempo: O(n * log n)

Espacio Auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por akhand_mishra y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *