Dada una array arr[] de longitud N , la tarea es maximizar la suma de todos los elementos de la array realizando las siguientes operaciones como máximo una vez.
- Elija un prefijo de la array y multiplique todos los elementos por -1.
- Elija un sufijo de la array y multiplique todos los elementos por -1.
Ejemplos:
Entrada: arr[] = {-1, -2, -3}
Salida: 6
Explicación:
Operación 1: Prefijo de array: {-1, -2, -3}
se puede multiplicar por -1 para obtener la suma máxima.
Array después de la operación: {1, 2, 3}
Suma = 1 + 2 + 3 = 6Entrada: arr[] = {-4, 2, 0, 5, 0}
Salida: 11
Explicación:
Operación 1: Prefijo de array: {-4}
se puede multiplicar por -1 para obtener la suma máxima.
Array después de la operación: {4, 2, 0, 5, 0}
Suma = 4 + 2 + 0 + 5 + 0 = 11
Enfoque: La observación clave en el problema es que si el rango elegido del prefijo y el sufijo se cruzan, entonces los elementos de la porción de intersección tienen el mismo signo. Debido a lo cual, siempre es mejor elegir rangos que no se intersecan de la array de prefijos y sufijos. A continuación se muestra la ilustración de los pasos:
- Se observa fácilmente que habrá una porción/subarreglo en el arreglo cuya suma es la misma que la original y la suma de los demás elementos se invierte. Entonces la nueva suma de la array será:
// X - Sum of subarray which is not in // the range of the prefix and suffix // S - Sum of the original array New Sum = X + -1*(S - X) = 2*X - S
- Por lo tanto, la idea es maximizar el valor de X para obtener la suma máxima porque S es el valor constante que no se puede cambiar. Esto se puede lograr con la ayuda del Algoritmo de Kadane .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// maximum sum of the array by
// multiplying the prefix and suffix
// of the array by -1
#include <bits/stdc++.h>
using namespace std;
// Kadane's algorithm to find
// the maximum subarray sum
int maxSubArraySum(int a[], int size)
{
int max_so_far = INT_MIN,
max_ending_here = 0;
// Loop to find the maximum subarray
// array sum in the given array
for (int i = 0; i < size; i++) {
max_ending_here =
max_ending_here + a[i];
if (max_ending_here < 0)
max_ending_here = 0;
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
}
return max_so_far;
}
// Function to find the maximum
// sum of the array by multiplying
// the prefix and suffix by -1
int maxSum(int a[], int n)
{
// Total initial sum
int S = 0;
// Loop to find the maximum
// sum of the array
for (int i = 0; i < n; i++)
S += a[i];
int X = maxSubArraySum(a, n);
// Maximum value
return 2 * X - S;
}
// Driver Code
int main()
{
int a[] = { -1, -2, -3 };
int n = sizeof(a) / sizeof(a[0]);
int max_sum = maxSum(a, n);
cout << max_sum;
return 0;
}
Java
// Java implementation to find the
// maximum sum of the array by
// multiplying the prefix and suffix
// of the array by -1
class GFG
{
// Kadane's algorithm to find
// the maximum subarray sum
static int maxSubArraySum(int a[], int size)
{
int max_so_far = Integer.MIN_VALUE,
max_ending_here = 0;
// Loop to find the maximum subarray
// array sum in the given array
for (int i = 0; i < size; i++) {
max_ending_here =
max_ending_here + a[i];
if (max_ending_here < 0)
max_ending_here = 0;
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
}
return max_so_far;
}
// Function to find the maximum
// sum of the array by multiplying
// the prefix and suffix by -1
static int maxSum(int a[], int n)
{
// Total initial sum
int S = 0;
int i;
// Loop to find the maximum
// sum of the array
for (i = 0; i < n; i++)
S += a[i];
int X = maxSubArraySum(a, n);
// Maximum value
return 2 * X - S;
}
// Driver Code
public static void main(String []args)
{
int a[] = { -1, -2, -3 };
int n = a.length;
int max_sum = maxSum(a, n);
System.out.print(max_sum);
}
}
// This code is contributed by chitranayal
Python3
# Python3 implementation to find the # maximum sum of the array by # multiplying the prefix and suffix # of the array by -1 # Kadane's algorithm to find # the maximum subarray sum def maxSubArraySum(a, size): max_so_far = -10**9 max_ending_here = 0 # Loop to find the maximum subarray # array sum in the given array for i in range(size): max_ending_here = max_ending_here + a[i] if (max_ending_here < 0): max_ending_here = 0 if (max_so_far < max_ending_here): max_so_far = max_ending_here return max_so_far # Function to find the maximum # sum of the array by multiplying # the prefix and suffix by -1 def maxSum(a, n): # Total initial sum S = 0 # Loop to find the maximum # sum of the array for i in range(n): S += a[i] X = maxSubArraySum(a, n) # Maximum value return 2 * X - S # Driver Code if __name__ == '__main__': a=[-1, -2, -3] n= len(a) max_sum = maxSum(a, n) print(max_sum) # This code is contributed by mohit kumar 29
C#
// C# implementation to find the
// maximum sum of the array by
// multiplying the prefix and suffix
// of the array by -1
using System;
class GFG
{
// Kadane's algorithm to find
// the maximum subarray sum
static int maxSubArraySum(int []a, int size)
{
int max_so_far = int.MinValue,
max_ending_here = 0;
// Loop to find the maximum subarray
// array sum in the given array
for (int i = 0; i < size; i++) {
max_ending_here =
max_ending_here + a[i];
if (max_ending_here < 0)
max_ending_here = 0;
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
}
return max_so_far;
}
// Function to find the maximum
// sum of the array by multiplying
// the prefix and suffix by -1
static int maxSum(int []a, int n)
{
// Total initial sum
int S = 0;
int i;
// Loop to find the maximum
// sum of the array
for (i = 0; i < n; i++)
S += a[i];
int X = maxSubArraySum(a, n);
// Maximum value
return 2 * X - S;
}
// Driver Code
public static void Main(String []args)
{
int []a = { -1, -2, -3 };
int n = a.Length;
int max_sum = maxSum(a, n);
Console.Write(max_sum);
}
}
// This code is contributed by sapnasingh4991
Javascript
<script>
// Javascript implementation to find the
// maximum sum of the array by
// multiplying the prefix and suffix
// of the array by -1
// Kadane's algorithm to find
// the maximum subarray sum
function maxSubArraySum(a, size)
{
var max_so_far = Number.MIN_VALUE,
max_ending_here = 0;
// Loop to find the maximum subarray
// array sum in the given array
for(i = 0; i < size; i++)
{
max_ending_here = max_ending_here + a[i];
if (max_ending_here < 0)
max_ending_here = 0;
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
}
return max_so_far;
}
// Function to find the maximum
// sum of the array by multiplying
// the prefix and suffix by -1
function maxSum(a, n)
{
// Total initial sum
var S = 0;
var i;
// Loop to find the maximum
// sum of the array
for(i = 0; i < n; i++)
S += a[i];
var X = maxSubArraySum(a, n);
// Maximum value
return 2 * X - S;
}
// Driver Code
var a = [ -1, -2, -3 ];
var n = a.length;
var max_sum = maxSum(a, n);
document.write(max_sum);
// This code is contributed by aashish1995
</script>
Producción:
6
Complejidad de tiempo: O(N)