Dada una array , arr[] de tamaño N , la tarea es encontrar la suma máxima posible de elementos de la array alternando los signos de los elementos de la array adyacentes.
Ejemplos:
Entrada: arr[] = { -2, 1, 0 }
Salida: 3
Explicación:
Alternar los signos de (arr[0], arr[1]) modifica arr[] a {2, -1, 0}.
Alternar los signos de (arr[1], arr[2]) modifica arr[] a {2, 1, 0}.
Por lo tanto, la salida requerida = (2 + 1 + 0) = 3, que es la suma máxima posible.Entrada: arr[] = { 1, 1, -2, -4, 5 }
Salida: 13
Explicación:
Alternar los signos de (arr[2], arr[3]) modifica arr[] a { 1, 1, 2 , 4, 5 }
Por lo tanto, la salida requerida = (1 + 1 + 2 + 4 + 5) = 13, que es la suma máxima posible.
Enfoque: El problema se puede resolver usando la técnica Greedy . La idea se basa en el hecho de que el recuento máximo de elementos negativos en la array después de alternar los signos de los elementos adyacentes no puede ser mayor que 1 . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos MaxAltSum , para almacenar la suma máxima posible de elementos de array alternando los signos de elementos adyacentes.
- Recorra la array y cuente el número de elementos negativos en la array.
- Si el recuento de elementos negativos en la array es par , entonces la suma máxima posible alternando los signos de los elementos de la array adyacentes es igual a la suma del valor absoluto de los elementos de la array, es decir, MaxAltSum = Σabs(arr[i])
- De lo contrario, la suma máxima posible obtenida de la array al alternar los signos de los elementos de la array adyacentes es igual a la suma del valor absoluto de todos los elementos de la array posibles, excepto el valor absoluto más pequeño de los elementos de la array. es decir, MaxAltSum = ((Σabs(arr[i])) – 2 * X) , donde X es el valor absoluto más pequeño de los elementos de la array.
- Finalmente, imprima el valor MaxAltSum .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum sum by alternating
// the signs of adjacent elements of the array
int findMaxSumByAlternatingSign(int arr[], int N)
{
// Stores count of negative
// elements in the array
int cntNeg = 0;
// Stores maximum sum by alternating
// the signs of adjacent elements
int MaxAltSum = 0;
// Stores smallest absolute
// value of array elements
int SmValue = 0;
// Stores sum of absolute
// value of array elements
int sum = 0;
// Traverse the array
for (int i = 0; i < N; i++) {
// If arr[i] is
// a negative number
if (arr[i] < 0) {
// Update cntNeg
cntNeg += 1;
}
// Update sum
sum += abs(arr[i]);
// Update SmValue
SmValue = min(SmValue,
abs(arr[i]));
}
// Update MaxAltSum
MaxAltSum = sum;
// If cntNeg is
// an odd number
if (cntNeg & 1) {
// Update MaxAltSum
MaxAltSum -= 2 * SmValue;
}
return MaxAltSum;
}
// Drivers Code
int main()
{
int arr[] = { 1, 1, -2, -4, 5 };
int N = sizeof(arr)
/ sizeof(arr[0]);
cout << findMaxSumByAlternatingSign(
arr, N);
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to find the maximum sum by alternating
// the signs of adjacent elements of the array
static int findMaxSumByAlternatingSign(int arr[],
int N)
{
// Stores count of negative
// elements in the array
int cntNeg = 0;
// Stores maximum sum by alternating
// the signs of adjacent elements
int MaxAltSum = 0;
// Stores smallest absolute
// value of array elements
int SmValue = 0;
// Stores sum of absolute
// value of array elements
int sum = 0;
// Traverse the array
for(int i = 0; i < N; i++)
{
// If arr[i] is
// a negative number
if (arr[i] < 0)
{
// Update cntNeg
cntNeg += 1;
}
// Update sum
sum += Math.abs(arr[i]);
// Update SmValue
SmValue = Math.min(SmValue,
Math.abs(arr[i]));
}
// Update MaxAltSum
MaxAltSum = sum;
// If cntNeg is
// an odd number
if (cntNeg % 2 == 1)
{
// Update MaxAltSum
MaxAltSum -= 2 * SmValue;
}
return MaxAltSum;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 1, -2, -4, 5 };
int N = arr.length;
System.out.print(findMaxSumByAlternatingSign(
arr, N));
}
}
// This code is contributed by jana_sayantan
Python3
# Python3 program to implement # the above approach # Function to find the maximum sum by # alternating the signs of adjacent # elements of the array def findMaxSumByAlternatingSign(arr, N): # Stores count of negative # elements in the array cntNeg = 0 # Stores maximum sum by alternating # the signs of adjacent elements MaxAltSum = 0 # Stores smallest absolute # value of array elements SmValue = 0 # Stores sum of absolute # value of array elements sum = 0 # Traverse the array for i in range(N): # If arr[i] is # a negative number if (arr[i] < 0): # Update cntNeg cntNeg += 1 # Update sum sum += abs(arr[i]) # Update SmValue SmValue = min(SmValue, abs(arr[i])) # Update MaxAltSum MaxAltSum = sum # If cntNeg is # an odd number if (cntNeg & 1): # Update MaxAltSum MaxAltSum -= 2 * SmValue return MaxAltSum # Driver Code if __name__ == '__main__': arr = [ 1, 1, -2, -4, 5 ] N = len(arr) print(findMaxSumByAlternatingSign(arr, N)) # This code is contributed by SURENDRA_GANGWAR
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to find the maximum sum by alternating
// the signs of adjacent elements of the array
static int findMaxSumByAlternatingSign(int []arr,
int N)
{
// Stores count of negative
// elements in the array
int cntNeg = 0;
// Stores maximum sum by alternating
// the signs of adjacent elements
int MaxAltSum = 0;
// Stores smallest absolute
// value of array elements
int SmValue = 0;
// Stores sum of absolute
// value of array elements
int sum = 0;
// Traverse the array
for(int i = 0; i < N; i++)
{
// If arr[i] is
// a negative number
if (arr[i] < 0)
{
// Update cntNeg
cntNeg += 1;
}
// Update sum
sum += Math.Abs(arr[i]);
// Update SmValue
SmValue = Math.Min(SmValue,
Math.Abs(arr[i]));
}
// Update MaxAltSum
MaxAltSum = sum;
// If cntNeg is
// an odd number
if (cntNeg % 2 == 1)
{
// Update MaxAltSum
MaxAltSum -= 2 * SmValue;
}
return MaxAltSum;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 1, 1, -2, -4, 5 };
int N = arr.Length;
Console.Write(findMaxSumByAlternatingSign(
arr, N));
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to find the maximum sum by alternating
// the signs of adjacent elements of the array
function findMaxSumByAlternatingSign(arr, N)
{
// Stores count of negative
// elements in the array
let cntNeg = 0;
// Stores maximum sum by alternating
// the signs of adjacent elements
let MaxAltSum = 0;
// Stores smallest absolute
// value of array elements
let SmValue = 0;
// Stores sum of absolute
// value of array elements
let sum = 0;
// Traverse the array
for(let i = 0; i < N; i++)
{
// If arr[i] is
// a negative number
if (arr[i] < 0)
{
// Update cntNeg
cntNeg += 1;
}
// Update sum
sum += Math.abs(arr[i]);
// Update SmValue
SmValue = Math.min(SmValue,
Math.abs(arr[i]));
}
// Update MaxAltSum
MaxAltSum = sum;
// If cntNeg is
// an odd number
if (cntNeg % 2 == 1)
{
// Update MaxAltSum
MaxAltSum -= 2 * SmValue;
}
return MaxAltSum;
}
// Driver Code
let arr = [ 1, 1, -2, -4, 5 ];
let N = arr.length;
document.write(findMaxSumByAlternatingSign(
arr, N));
// This code is contributed by souravghosh0416.
</script>
Producción:
13
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por reapedjuggler y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA