Dada una array A[][] de dimensiones M × N , la tarea es encontrar la suma máxima posible de una array seleccionando repetidamente dos elementos de array adyacentes y multiplicando ambos valores por -1.
Ejemplos:
Entrada: A[ ][ ] = {{4, -8, 6}, {3, 7, 2}}
Salida: 26
Explicación:
Multiplique mat[0][1] y mat[0][2] por -1 . La array se modifica a A[][] = {{4, 8, -6}, {3, 7, 2}}.
Multiplique mat[0][2] y mat[1][2] por -1. La array se modifica a A[][] = {{4, 8, 6}, {3, 7, -2}}.
Por tanto, suma de la array = 26, que es la máxima suma posible.Entrada: A[ ][ ] = {{2, 9, -5}, {6, 1, 3}, {-7, 4, 8}} Salida: 45 Explicación: Multiplique
mat [
0
][2] y mat [1][2] por -1. La array se modifica a A[][] = {{2, 9, 5}, {6, 1, -3}, {-7, 4, 8}} .
Multiplique mat[1][1] y mat[1][2] por -1. La array se modifica a A[][] = {{2, 9, 5}, {6, -1, 3}, {-7, 4, 8}} .
Multiplique mat[1][1] y mat[2][1] por -1. La array se modifica a A[][] = {{2, 9, 5}, {6, 1, 3}, {-7, -4, 8}} .
Multiplique mat[2][0] y mat[2][1] por -1. La array se modifica a A[][] = {{2, 9, 5}, {6, 1, 3}, {7, 4, 8}} .
Por tanto, suma de la array = 45, que es la máxima suma posible.
Enfoque: Para maximizar la suma de la array dada, realice las operaciones dadas de modo que el elemento más pequeño en una fila o columna sea negativo (si no es posible hacer que todos los elementos de fila y columna sean positivos). Siga los pasos a continuación para maximizar la suma:
- Sea x el número de celdas con valores negativos . Si x es 0 , es decir, no hay valores negativos, entonces la suma de la array ya es la máxima posible.
- De lo contrario, tome cualquier valor negativo de la array y realice las operaciones dadas en ese elemento y cualquiera de sus celdas adyacentes. Esto da como resultado que el elemento elegido se vuelva positivo.
- Ahora bien, si el valor del elemento adyacente elegido es negativo, se volverá positivo o viceversa. De esta forma, en cada turno se pueden convertir en positivos dos valores negativos. Ahora surgen los siguientes dos casos:
- Si x es par: En este caso, después de x/2 vueltas, todos los valores negativos pueden convertirse en positivos. Por lo tanto, la suma máxima posible es igual a la suma de los valores absolutos de todas las celdas.
- Si x es impar: en este caso, quedará un valor negativo después de realizar las operaciones de la manera descrita anteriormente. Ahora, para maximizar la suma, el valor que se resta o que tiene un signo negativo debe minimizarse. Para hacer esto, mueva el signo negativo a la celda que tiene el valor absoluto mínimo, digamos minVal . Por lo tanto, la suma máxima posible es la suma de los valores absolutos de todas las celdas: 2*minVal .
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 calculate maximum sum
// possible of a matrix by multiplying
// pairs of adjacent elements with -1
// any number of times (possibly zero)
void getMaxSum(vector<vector<int> > A,
int M, int N)
{
// Store the maximum sum
// of matrix possible
int sum = 0;
// Stores the count of
// negative values in the matrix
int negative = 0;
// Store minimum absolute
// value present in the matrix
int minVal = INT_MAX;
// Traverse the matrix row-wise
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
// Update sum
sum += abs(A[i][j]);
// If current element is negative,
// increment the negative count
if (A[i][j] < 0) {
negative++;
}
// If current value is less than
// the overall minimum in A[],
// update the overall minimum
minVal = min(minVal, abs(A[i][j]));
}
}
// If there are odd number of negative
// values, then the answer will be
// sum of the absolute values of
// all elements - 2* minVal
if (negative % 2) {
sum -= 2 * minVal;
}
// Print maximum sum
cout << sum;
}
// Driver Code
int main()
{
// Given matrix
vector<vector<int> > A = {
{ 4, -8, 6 },
{ 3, 7, 2 }
};
// Dimensions of matrix
int M = A.size();
int N = A[0].size();
getMaxSum(A, M, N);
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
class GFG
{
static void getMaxSum(int[][] A, int M, int N)
{
// Store the maximum sum
// of matrix possible
int sum = 0;
// Stores the count of
// negative values in the matrix
int negative = 0;
// Store minimum absolute
// value present in the matrix
int minVal = Integer.MAX_VALUE;
// Traverse the matrix row-wise
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
// Update sum
sum += Math.abs(A[i][j]);
// If current element is negative,
// increment the negative count
if (A[i][j] < 0) {
negative++;
}
// If current value is less than
// the overall minimum in A[],
// update the overall minimum
minVal
= Math.min(minVal, Math.abs(A[i][j]));
}
}
// If there are odd number of negative
// values, then the answer will be
// sum of the absolute values of
// all elements - 2* minVal
if (negative % 2 != 0) {
sum -= 2 * minVal;
}
// Print maximum sum
System.out.println(sum);
}
// Driver Code
public static void main(String[] args)
{
// Given matrix
int[][] A = { { 4, -8, 6 }, { 3, 7, 2 } };
// Dimensions of matrix
int M = A.length;
int N = A[0].length;
getMaxSum(A, M, N);
}
}
// This code is contributed by aditya7409.
Python3
# Python3 program to implement # the above approach import sys # Function to calculate maximum sum # possible of a matrix by multiplying # pairs of adjacent elements with -1 # any number of times (possibly zero) def getMaxSum(A, M, N): # Store the maximum sum # of matrix possible sum = 0 # Stores the count of # negative values in the matrix negative = 0 # Store minimum absolute # value present in the matrix minVal = sys.maxsize # Traverse the matrix row-wise for i in range(M): for j in range(N): # Update sum sum += abs(A[i][j]) # If current element is negative, # increment the negative count if (A[i][j] < 0): negative +=1 # If current value is less than # the overall minimum in A[], # update the overall minimum minVal = min(minVal, abs(A[i][j])) # If there are odd number of negative # values, then the answer will be # sum of the absolute values of # all elements - 2* minVal if (negative % 2): sum -= 2 * minVal # Print maximum sum print(sum) # Driver Code if __name__ == '__main__': # Given matrix A = [[4, -8, 6], [3, 7, 2]] # Dimensions of matrix M = len(A) N = len(A[0]) getMaxSum(A, M, N) # This code is contributed by ipg2016107.
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to calculate maximum sum
// possible of a matrix by multiplying
// pairs of adjacent elements with -1
// any number of times (possibly zero)
static void getMaxSum(int[,] A, int M, int N)
{
// Store the maximum sum
// of matrix possible
int sum = 0;
// Stores the count of
// negative values in the matrix
int negative = 0;
// Store minimum absolute
// value present in the matrix
int minVal = Int32.MaxValue;
// Traverse the matrix row-wise
for(int i = 0; i < M; i++)
{
for(int j = 0; j < N; j++)
{
// Update sum
sum += Math.Abs(A[i, j]);
// If current element is negative,
// increment the negative count
if (A[i, j] < 0)
{
negative++;
}
// If current value is less than
// the overall minimum in A[],
// update the overall minimum
minVal = Math.Min(minVal,
Math.Abs(A[i, j]));
}
}
// If there are odd number of negative
// values, then the answer will be
// sum of the absolute values of
// all elements - 2* minVal
if (negative % 2 != 0)
{
sum -= 2 * minVal;
}
// Print maximum sum
Console.Write(sum);
}
// Driver Code
public static void Main()
{
// Given matrix
int[, ] A = { { 4, -8, 6 },
{ 3, 7, 2 } };
// Dimensions of matrix
int M = A.GetLength(0);
int N = A.GetLength(1);
getMaxSum(A, M, N);
}
}
// This code is contributed by chitranayal
Javascript
<script>
//java script code
function getMaxSum(A,M,N)
{
// Store the maximum sum
// of matrix possible
let sum = 0;
// Stores the count of
// negative values in the matrix
let negative = 0;
// Store minimum absolute
// value present in the matrix
let minVal = Number.MAX_VALUE;
// Traverse the matrix row-wise
for (let i = 0; i < M; i++) {
for (let j = 0; j < N; j++) {
// Update sum
sum += Math.abs(A[i][j]);
// If current element is negative,
// increment the negative count
if (A[i][j] < 0) {
negative++;
}
// If current value is less than
// the overall minimum in A[],
// update the overall minimum
minVal
= Math.min(minVal, Math.abs(A[i][j]));
}
}
// If there are odd number of negative
// values, then the answer will be
// sum of the absolute values of
// all elements - 2* minVal
if (negative % 2 != 0) {
sum -= 2 * minVal;
}
// Print maximum sum
document.write(sum);
}
// Driver Code
// Given matrix
let A = [[4, -8, 6 ], [ 3, 7, 2 ]];
// Dimensions of matrix
let M = A.length;
let N = A[0].length;
getMaxSum(A, M, N);
// This code is contributed by sravan kumar Gottumukkala
</script>
Producción:
26
Complejidad temporal: O(M*N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por sunidhichandra27 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA