Dada una array de tamaño n y un número k. Debemos modificar la array K varias 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:
Entrada: arr[] = {-2, 0, 5, -1, 2}, K = 4
Salida: 10
Explicación:
1. Reemplace (-2) por -(-2), la array se convierte en {2, 0, 5 , -1, 2}
2. Reemplace (-1) por -(-1), la array se convierte en {2, 0, 5, 1, 2}
3. Reemplace (0) por -(0), la array se convierte en {2, 0, 5, 1, 2}
4. Reemplace (0) por -(0), la array se convierte en {2, 0, 5, 1, 2}Entrada: arr[] = {9, 8, 8, 5}, K = 3
Salida: 20
Enfoque ingenuo: este problema tiene una solución muy simple , solo tenemos que 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. Un caso interesante es que una vez que el elemento mínimo se convierte en 0, no necesitamos hacer más cambios.
Implementación:
C++
// C++ program to maximize array sum after // k operations. #include <bits/stdc++.h> using namespace std; // This function does k operations on array in a way that // maximize the array sum. index --> stores the index of // current minimum element for j'th operation int maximumSum(int arr[], int n, int k) { // Modify array K number of times for (int i = 1; i <= k; i++) { int min = INT_MAX; int index = -1; // Find minimum element in array for current // operation and modify it i.e; arr[j] --> -arr[j] for (int j = 0; j < n; j++) { if (arr[j] < min) { min = arr[j]; index = j; } } // this the condition if we find 0 as minimum // element, so it will useless to replace 0 by -(0) // for remaining operations if (min == 0) break; // Modify element of array arr[index] = -arr[index]; } // Calculate sum of array int sum = 0; for (int i = 0; i < n; i++) sum += arr[i]; return sum; } // Driver code int main() { int arr[] = { -2, 0, 5, -1, 2 }; int k = 4; int n = sizeof(arr) / sizeof(arr[0]); cout << maximumSum(arr, n, k); return 0; } // This code is contributed by Aditya Kumar (adityakumar129)
C
// C program to maximize array sum after // k operations. #include<stdio.h> #include<stdlib.h> #include <limits.h> // This function does k operations on array in a way that // maximize the array sum. index --> stores the index of // current minimum element for j'th operation int maximumSum(int arr[], int n, int k) { // Modify array K number of times for (int i = 1; i <= k; i++) { int min = INT_MAX; int index = -1; // Find minimum element in array for current // operation and modify it i.e; arr[j] --> -arr[j] for (int j = 0; j < n; j++) { if (arr[j] < min) { min = arr[j]; index = j; } } // this the condition if we find 0 as minimum // element, so it will useless to replace 0 by -(0) // for remaining operations if (min == 0) break; // Modify element of array arr[index] = -arr[index]; } // Calculate sum of array int sum = 0; for (int i = 0; i < n; i++) sum += arr[i]; return sum; } // Driver code int main() { int arr[] = { -2, 0, 5, -1, 2 }; int k = 4; int n = sizeof(arr) / sizeof(arr[0]); printf("%d",maximumSum(arr, n, k)); return 0; } // This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program to maximize array // sum after k operations. class GFG { // This function does k operations on array in a way // that maximize the array sum. index --> stores the // index of current minimum element for j'th operation static int maximumSum(int arr[], int n, int k) { // Modify array K number of times for (int i = 1; i <= k; i++) { int min = +2147483647; int index = -1; // Find minimum element in array for current // operation and modify it i.e; arr[j] --> -arr[j] for (int j = 0; j < n; j++) { if (arr[j] < min) { min = arr[j]; index = j; } } // this the condition if we find 0 as minimum // element, so it will useless to replace 0 by // -(0) for remaining operations if (min == 0) break; // Modify element of array arr[index] = -arr[index]; } // Calculate sum of array int sum = 0; for (int i = 0; i < n; i++) sum += arr[i]; return sum; } // Driver code public static void main(String arg[]) { int arr[] = { -2, 0, 5, -1, 2 }; int k = 4; int n = arr.length; System.out.print(maximumSum(arr, n, k)); } } // This code is contributed by Aditya Kumar (adityakumar129)
Python3
# Python3 program to maximize # array sum after k operations. # This function does k operations on array # in a way that maximize the array sum. # index --> stores the index of current # minimum element for j'th operation def maximumSum(arr, n, k): # Modify array K number of times for i in range(1, k + 1): min = +2147483647 index = -1 # Find minimum element in array for # current operation and modify it # i.e; arr[j] --> -arr[j] for j in range(n): if (arr[j] < min): min = arr[j] index = j # this the condition if we find 0 as # minimum element, so it will useless to # replace 0 by -(0) for remaining operations if (min == 0): break # Modify element of array arr[index] = -arr[index] # Calculate sum of array sum = 0 for i in range(n): sum += arr[i] return sum # Driver code arr = [-2, 0, 5, -1, 2] k = 4 n = len(arr) print(maximumSum(arr, n, k)) # This code is contributed by Anant Agarwal.
C#
// C# program to maximize array // sum after k operations. using System; class GFG { // This function does k operations // on array in a way that maximize // the array sum. index --> stores // the index of current minimum // element for j'th operation static int maximumSum(int[] arr, int n, int k) { // Modify array K number of times for (int i = 1; i <= k; i++) { int min = +2147483647; int index = -1; // Find minimum element in array for // current operation and modify it // i.e; arr[j] --> -arr[j] for (int j = 0; j < n; j++) { if (arr[j] < min) { min = arr[j]; index = j; } } // this the condition if we find // 0 as minimum element, so it // will useless to replace 0 by -(0) // for remaining operations if (min == 0) break; // Modify element of array arr[index] = -arr[index]; } // Calculate sum of array int sum = 0; for (int i = 0; i < n; i++) sum += arr[i]; return sum; } // Driver code public static void Main() { int[] arr = { -2, 0, 5, -1, 2 }; int k = 4; int n = arr.Length; Console.Write(maximumSum(arr, n, k)); } } // This code is contributed by Nitin Mittal.
PHP
<?php // PHP program to maximize // array sum after k operations. // This function does k operations // on array in a way that maximize // the array sum. index --> stores // the index of current minimum // element for j'th operation function maximumSum($arr, $n, $k) { $INT_MAX = 0; // Modify array K // number of times for ($i = 1; $i <= $k; $i++) { $min = $INT_MAX; $index = -1; // Find minimum element in // array for current operation // and modify it i.e; // arr[j] --> -arr[j] for ($j = 0; $j < $n; $j++) { if ($arr[$j] < $min) { $min = $arr[$j]; $index = $j; } } // this the condition if we // find 0 as minimum element, so // it will useless to replace 0 // by -(0) for remaining operations if ($min == 0) break; // Modify element of array $arr[$index] = -$arr[$index]; } // Calculate sum of array $sum = 0; for ($i = 0; $i < $n; $i++) $sum += $arr[$i]; return $sum; } // Driver Code $arr = array(-2, 0, 5, -1, 2); $k = 4; $n = sizeof($arr) / sizeof($arr[0]); echo maximumSum($arr, $n, $k); // This code is contributed // by nitin mittal. ?>
Javascript
<script> // Javascript program to maximize array // sum after k operations. // This function does k operations // on array in a way that maximize // the array sum. index --> stores // the index of current minimum // element for j'th operation function maximumSum(arr, n, k) { // Modify array K number of times for(let i = 1; i <= k; i++) { let min = +2147483647; let index = -1; // Find minimum element in array for // current operation and modify it // i.e; arr[j] --> -arr[j] for(let j = 0; j < n; j++) { if (arr[j] < min) { min = arr[j]; index = j; } } // This the condition if we find 0 as // minimum element, so it will useless to // replace 0 by -(0) for remaining operations if (min == 0) break; // Modify element of array arr[index] = -arr[index]; } // Calculate sum of array let sum = 0; for(let i = 0; i < n; i++) sum += arr[i]; return sum; } // Driver code let arr = [ -2, 0, 5, -1, 2 ]; let k = 4; let n = arr.length; document.write(maximumSum(arr, n, k)); // This code is contributed by code_hunt </script>
10
Complejidad temporal: O(k*n)
Espacio auxiliar: O(1)
Enfoque 2 (usando la ordenación): cuando existe la necesidad de negar como máximo k elementos.
Siga los pasos a continuación para resolver este problema:
- Ordena la array dada arr .
- Luego, para un valor dado de k, iterar a través de la array hasta que k permanezca mayor que 0. Si el valor de la array en cualquier índice es menor que 0 , cambiaremos su signo y disminuiremos k en 1 .
- Si encontramos un 0 en la array, inmediatamente estableceremos k igual a 0 para maximizar nuestro resultado.
- En algunos casos, si tenemos todos los valores en una array mayores que 0, cambiaremos el signo de los valores positivos, ya que nuestra array ya está ordenada, cambiaremos los signos de los valores más bajos presentes en la array, lo que eventualmente maximizará nuestra suma.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find maximum array sum after at most k // negations. #include <bits/stdc++.h> using namespace std; int sol(int arr[], int n, int k) { int sum = 0; int i = 0; // Sorting given array using in-built sort function sort(arr, arr + n); while (k > 0) { // If we find a 0 in our sorted array, we stop if (arr[i] >= 0) k = 0; else { arr[i] = (-1) * arr[i]; k = k - 1; } i++; } // Calculating sum for (int j = 0; j < n; j++) sum += arr[j]; return sum; } // Driver code int main() { int arr[] = { -2, 0, 5, -1, 2 }; int n = sizeof(arr) / sizeof(arr[0]); cout << sol(arr, n, 4) << endl; return 0; } // This code is contributed by Aditya Kumar (adityakumar129)
C
// C++ program to find maximum array sum after at most k // negations. #include <stdio.h> #include <stdlib.h> int cmpfunc(const void* a, const void* b) { return (*(int*)a - *(int*)b); } int sol(int arr[], int n, int k) { int sum = 0; int i = 0; // Sorting given array using in-built sort function qsort(arr, n, sizeof(int), cmpfunc); while (k > 0) { // If we find a 0 in our sorted array, we stop if (arr[i] >= 0) k = 0; else { arr[i] = (-1) * arr[i]; k = k - 1; } i++; } // Calculating sum for (int j = 0; j < n; j++) sum += arr[j]; return sum; } // Driver code int main() { int arr[] = { -2, 0, 5, -1, 2 }; int n = sizeof(arr) / sizeof(arr[0]); printf("%d", sol(arr, n, 4)); return 0; } // This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program to find maximum array sum // after at most k negations. import java.util.Arrays; public class GFG { static int sol(int arr[], int k) { // Sorting given array using in-built java sort // function Arrays.sort(arr); int sum = 0; int i = 0; while (k > 0) { // If we find a 0 in our sorted array, we stop if (arr[i] >= 0) k = 0; else { arr[i] = (-1) * arr[i]; k = k - 1; } i++; } // Calculating sum for (int j = 0; j < arr.length; j++) sum += arr[j]; return sum; } // Driver Code public static void main(String[] args) { int arr[] = { -2, 0, 5, -1, 2 }; System.out.println(sol(arr, 4)); } } // This code is contributed by Aditya Kumar (adityakumar129)
Python3
# Python3 program to find maximum array # sum after at most k negations def sol(arr, k): # Sorting given array using # in-built java sort function arr.sort() Sum = 0 i = 0 while (k > 0): # If we find a 0 in our # sorted array, we stop if (arr[i] >= 0): k = 0 else: arr[i] = (-1) * arr[i] k = k - 1 i += 1 # Calculating sum for j in range(len(arr)): Sum += arr[j] return Sum # Driver code arr = [-2, 0, 5, -1, 2] print(sol(arr, 4)) # This code is contributed by avanitrachhadiya2155
C#
// C# program to find maximum array sum // after at most k negations. using System; class GFG{ static int sol(int []arr, int k) { // Sorting given array using // in-built java sort function Array.Sort(arr); int sum = 0; int i = 0; while (k > 0) { // If we find a 0 in our // sorted array, we stop if (arr[i] >= 0) k = 0; else { arr[i] = (-1) * arr[i]; k = k - 1; } i++; } // Calculating sum for(int j = 0; j < arr.Length; j++) { sum += arr[j]; } return sum; } // Driver code public static void Main(string[] args) { int []arr = { -2, 0, 5, -1, 2 }; Console.Write(sol(arr, 4)); } } // This code is contributed by rutvik_56
Javascript
<script> // JavaScript program to find maximum array sum // after at most k negations. function sol(arr, k) { // Sorting given array using in-built // java sort function arr.sort(); let sum = 0; let i = 0; while (k > 0) { // If we find a 0 in our // sorted array, we stop if (arr[i] >= 0) k = 0; else { arr[i] = (-1) * arr[i]; k = k - 1; } i++; } // Calculating sum for (let j = 0; j < arr.length; j++) { sum += arr[j]; } return sum; } // Driver code let arr = [ -2, 0, 5, -1, 2 ]; document.write(sol(arr, 4)); // This code is contributed by souravghosh0416. </script>
10
Complejidad de tiempo: O(n*logn)
Espacio auxiliar: O(1)
Enfoque 3 (usando Ordenar):
El enfoque anterior 2 es óptimo cuando existe la necesidad de negar como máximo k elementos. Para resolver cuando hay exactamente k negaciones , el algoritmo se da a continuación.
- Ordene la array en orden ascendente. Inicializar i = 0.
- Incremente i y multiplique todos los elementos negativos por -1 hasta que k se convierta o se alcance un elemento positivo.
- Compruebe si se ha producido el final de la array. Si es verdadero, vaya al (n-1) elemento.
- Si k ==0 o k es par, devuelve la suma de todos los elementos. De lo contrario, multiplique el absoluto del mínimo de i-ésimo o (i-1) ésimo elemento por -1.
- Devuelve la suma de la array.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to calculate sum of the array long long int sumArray(long long int* arr, int n) { long long int sum = 0; // Iterate from 0 to n - 1 for (int i = 0; i < n; i++) sum += arr[i]; return sum; } // Function to maximize sum long long int maximizeSum(long long int arr[], int n, int k) { sort(arr, arr + n); int i = 0; // Iterate from 0 to n - 1 for (i = 0; i < n; i++) { if (k && arr[i] < 0) { arr[i] *= -1; k--; continue; } break; } if (i == n) i--; if (k == 0 || k % 2 == 0) return sumArray(arr, n); if (i != 0 && abs(arr[i]) >= abs(arr[i - 1])) i--; arr[i] *= -1; return sumArray(arr, n); } // Driver Code int main() { int n = 5; int k = 4; long long int arr[5] = { -2, 0, 5, -1, 2 }; // Function Call cout << maximizeSum(arr, n, k) << endl; return 0; } // This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program for the above approach import java.util.*; class GFG { // Function to calculate sum of the array static int sumArray(int[] arr, int n) { int sum = 0; // Iterate from 0 to n - 1 for (int i = 0; i < n; i++) sum += arr[i]; return sum; } // Function to maximize sum static int maximizeSum(int arr[], int n, int k) { Arrays.sort(arr); int i = 0; // Iterate from 0 to n - 1 for (i = 0; i < n; i++) { if (k != 0 && arr[i] < 0) { arr[i] *= -1; k--; continue; } break; } if (i == n) i--; if (k == 0 || k % 2 == 0) return sumArray(arr, n); if (i != 0 && Math.abs(arr[i]) >= Math.abs(arr[i - 1])) i--; arr[i] *= -1; return sumArray(arr, n); } // Driver Code public static void main(String args[]) { int n = 5; int arr[] = { -2, 0, 5, -1, 2 }; int k = 4; // Function Call System.out.print(maximizeSum(arr, n, k)); } } // This code is contributed by Aditya Kumar (adityakumar129)
Python3
# Python3 program for the above approach # Function to calculate sum of the array def sumArray(arr, n): sum = 0 # Iterate from 0 to n - 1 for i in range(n): sum += arr[i] return sum # Function to maximize sum def maximizeSum(arr, n, k): arr.sort() i = 0 # Iterate from 0 to n - 1 for i in range(n): if (k and arr[i] < 0): arr[i] *= -1 k -= 1 continue break if (i == n): i -= 1 if (k == 0 or k % 2 == 0): return sumArray(arr, n) if (i != 0 and abs(arr[i]) >= abs(arr[i - 1])): i -= 1 arr[i] *= -1 return sumArray(arr, n) # Driver Code n = 5 k = 4 arr = [ -2, 0, 5, -1, 2 ] # Function Call print(maximizeSum(arr, n, k)) # This code is contributed by rohitsingh07052
C#
// C# program for the above approach using System; class GFG{ // Function to calculate sum of the array static int sumArray( int[] arr, int n) { int sum = 0; // Iterate from 0 to n - 1 for(int i = 0; i < n; i++) { sum += arr[i]; } return sum; } // Function to maximize sum static int maximizeSum(int[] arr, int n, int k) { Array.Sort(arr); int i = 0; // Iterate from 0 to n - 1 for(i = 0; i < n; i++) { if (k != 0 && arr[i] < 0) { arr[i] *= -1; k--; continue; } break; } if (i == n) i--; if (k == 0 || k % 2 == 0) { return sumArray(arr, n); } if (i != 0 && Math.Abs(arr[i]) >= Math.Abs(arr[i - 1])) { i--; } arr[i] *= -1; return sumArray(arr, n); } // Driver Code static public void Main() { int n = 5; int[] arr = { -2, 0, 5, -1, 2 }; int k = 4; // Function Call Console.Write(maximizeSum(arr, n, k)); } } // This code is contributed by shubhamsingh10
Javascript
<script> // Javascript program for the above approach // Function to calculate sum of the array function sumArray(arr,n) { let sum = 0; // Iterate from 0 to n - 1 for(let i = 0; i < n; i++) { sum += arr[i]; } return sum; } // Function to maximize sum function maximizeSum(arr,n,k) { (arr).sort(function(a,b){return a-b;}); let i = 0; // Iterate from 0 to n - 1 for(i = 0; i < n; i++) { if (k != 0 && arr[i] < 0) { arr[i] *= -1; k--; continue; } break; } if (i == n) i--; if (k == 0 || k % 2 == 0) { return sumArray(arr, n); } if (i != 0 && Math.abs(arr[i]) >= Math.abs(arr[i - 1])) { i--; } arr[i] *= -1; return sumArray(arr, n); } // Driver Code let n = 5; let k = 4; let arr=[ -2, 0, 5, -1, 2 ]; // Function Call document.write(maximizeSum(arr, n, k)); // This code is contributed by ab2127 </script>
C
// C program for the above approach #include <stdio.h> #include<stdlib.h> // Function to calculate sum of the array long long int sumArray(long long int* arr, int n) { long long int sum = 0; // Iterate from 0 to n - 1 for (int i = 0; i < n; i++) sum += arr[i]; return sum; } void merge(long long int arr[], int l, int m, int r) { int i, j, k; int n1 = m - l + 1; int n2 = r - m; /* create temp arrays */ int L[n1], R[n2]; /* Copy data to temp arrays L[] and R[] */ for (i = 0; i < n1; i++) L[i] = arr[l + i]; for (j = 0; j < n2; j++) R[j] = arr[m + 1 + j]; /* Merge the temp arrays back into arr[l..r]*/ i = 0; // Initial index of first subarray j = 0; // Initial index of second subarray k = l; // Initial index of merged subarray while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } /* Copy the remaining elements of L[], if there are any */ while (i < n1) { arr[k] = L[i]; i++; k++; } /* Copy the remaining elements of R[], if there are any */ while (j < n2) { arr[k] = R[j]; j++; k++; } } /* l is for left index and r is right index of the sub-array of arr to be sorted */ void mergeSort(long long int arr[], int l, int r) { if (l < r) { // Same as (l+r)/2, but avoids overflow for // large l and h int m = l + (r - l) / 2; // Sort first and second halves mergeSort(arr, l, m); mergeSort(arr, m + 1, r); merge(arr, l, m, r); } } // Function to maximize sum long long int maximizeSum(long long int arr[], int n, int k) { mergeSort(arr,0,n-1); int i = 0; // Iterate from 0 to n - 1 for (i = 0; i < n; i++) { if (k && arr[i] < 0) { arr[i] *= -1; k--; continue; } break; } if (i == n) i--; if (k == 0 || k % 2 == 0) return sumArray(arr, n); if (i != 0 && abs(arr[i]) >= abs(arr[i - 1])) i--; arr[i] *= -1; return sumArray(arr, n); } // Driver Code int main() { int n = 5; int k = 4; long long int arr[] = { -2, 0, 5, -1, 2 }; // Function Call printf("%lld",maximizeSum(arr,n,k)); return 0; }
10
Complejidad de tiempo: O(n*logn)
Espacio auxiliar: O(1)
Maximizar la suma de arreglos después de K negaciones | conjunto 2
Este artículo es una contribución de Shashank Mishra (Gullu) . 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.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA