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 ,
- Si count ≥ k entonces el signo de exactamente k números negativos cambiará comenzando desde el más pequeño.
- 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.
- 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