Dada una array de enteros. La tarea es encontrar la suma máxima de todos los elementos de la array después de realizar las dos operaciones dadas una vez cada una.
Las operaciones son:
1. Seleccione algunos elementos continuos (posiblemente ninguno) desde el principio de la array y multiplíquelos por -1.
2. Seleccione algunos elementos continuos (posiblemente ninguno) del final de la array y multiplíquelos por -1.
Ejemplos:
Input : arr[] = {-1, 10, -5, 10, -2}
Output : 18
After 1st operation : 1 10 -5 10 -2
After 2nd operation : 1 10 -5 10 2
Input : arr[] = {-9, -8, -7}
Output : 24
After 1st operation : 9 8 -7
After 2nd operation : 9 8 7
Planteamiento: Este problema se puede resolver en tiempo lineal, utilizando la siguiente idea:
- Deje que la suma de los elementos A1 .. An sea igual a S. Luego, al invertir los signos, obtenemos -A1, -A2 .. -An, y la suma se cambia a partir de entonces a -S, es decir, la suma de los elementos en el segmento simplemente cambiará su signo al invertir los signos de todo el segmento.
- Considere el problema inicial de la siguiente manera: elija una subsecuencia consecutiva e invierta todos los números restantes.
- Encuentre la suma máxima del subarreglo usando el algoritmo de Kadane .
- Mantenga ese subarreglo intacto y multiplique el resto por -1.
- Considerando la suma de todo el arreglo como S, y el subarreglo contiguo de suma más grande como S1, la suma total será igual a -(S-S1) + S1 = 2*S1 – S. Esta es la suma requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find the maximum
// sum after given operations
#include <bits/stdc++.h>
using namespace std;
// Function to calculate Maximum Subarray Sum
// or Kadane's Algorithm
int maxSubArraySum(int a[], int size)
{
int max_so_far = INT_MIN, max_ending_here = 0;
for (int i = 0; i < size; i++) {
max_ending_here = max_ending_here + a[i];
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
if (max_ending_here < 0)
max_ending_here = 0;
}
return max_so_far;
}
// Function to find the maximum
// sum after given operations
int maxSum(int a[], int n)
{
// To store sum of all elements
int S = 0;
// Maximum sum of a subarray
int S1 = maxSubArraySum(a, n);
// Calculate the sum of all elements
for (int i = 0; i < n; i++)
S += a[i];
return (2 * S1 - S);
}
// Driver Code
int main()
{
int a[] = { -35, 32, -24, 0, 27, -10, 0, -19 };
// size of an array
int n = sizeof(a) / sizeof(a[0]);
cout << maxSum(a, n);
return 0;
}
Java
// Java program to find the maximum
// sum after given operations
import java.io.*;
class GFG {
// Function to calculate Maximum Subarray Sum
// or Kadane's Algorithm
static int maxSubArraySum(int a[], int size)
{
int max_so_far = Integer.MIN_VALUE, max_ending_here = 0;
for (int i = 0; i < size; i++) {
max_ending_here = max_ending_here + a[i];
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
if (max_ending_here < 0)
max_ending_here = 0;
}
return max_so_far;
}
// Function to find the maximum
// sum after given operations
static int maxSum(int a[], int n)
{
// To store sum of all elements
int S = 0;
// Maximum sum of a subarray
int S1 = maxSubArraySum(a, n);
// Calculate the sum of all elements
for (int i = 0; i < n; i++)
S += a[i];
return (2 * S1 - S);
}
// Driver Code
public static void main (String[] args) {
int a[] = { -35, 32, -24, 0, 27, -10, 0, -19 };
// size of an array
int n = a.length;
System.out.println( maxSum(a, n));
}
}
// This code is contributed by inder_verma
Python3
# Python3 program to find the maximum # sum after given operations import sys # Function to calculate Maximum # Subarray Sum or Kadane's Algorithm def maxSubArraySum(a, size) : max_so_far = -(sys.maxsize - 1) max_ending_here = 0 for i in range(size) : max_ending_here = max_ending_here + a[i] if (max_so_far < max_ending_here) : max_so_far = max_ending_here if (max_ending_here < 0) : max_ending_here = 0 return max_so_far # Function to find the maximum # sum after given operations def maxSum(a, n) : # To store sum of all elements S = 0; # Maximum sum of a subarray S1 = maxSubArraySum(a, n) # Calculate the sum of all elements for i in range(n) : S += a[i] return (2 * S1 - S) # Driver Code if __name__ == "__main__" : a = [ -35, 32, -24, 0, 27, -10, 0, -19 ] # size of an array n = len(a) print(maxSum(a, n)) # This code is contributed by Ryuga
C#
// C# program to find the maximum
// sum after given operations
using System;
class GFG {
// Function to calculate Maximum Subarray Sum
// or Kadane's Algorithm
static int maxSubArraySum(int []a, int size)
{
int max_so_far = int.MinValue, max_ending_here = 0;
for (int i = 0; i < size; i++) {
max_ending_here = max_ending_here + a[i];
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
if (max_ending_here < 0)
max_ending_here = 0;
}
return max_so_far;
}
// Function to find the maximum
// sum after given operations
static int maxSum(int []a, int n)
{
// To store sum of all elements
int S = 0;
// Maximum sum of a subarray
int S1 = maxSubArraySum(a, n);
// Calculate the sum of all elements
for (int i = 0; i < n; i++)
S += a[i];
return (2 * S1 - S);
}
// Driver Code
public static void Main () {
int []a = { -35, 32, -24, 0, 27, -10, 0, -19 };
// size of an array
int n = a.Length;
Console.WriteLine( maxSum(a, n));
}
}
// This code is contributed by inder_verma
PHP
<?php
// PHP program to find the maximum
// sum after given operations
// Function to calculate Maximum Subarray
// Sum or Kadane's Algorithm
function maxSubArraySum($a, $size)
{
$max_so_far = PHP_INT_MIN;
$max_ending_here = 0;
for ($i = 0; $i < $size; $i++)
{
$max_ending_here = $max_ending_here + $a[$i];
if ($max_so_far < $max_ending_here)
$max_so_far = $max_ending_here;
if ($max_ending_here < 0)
$max_ending_here = 0;
}
return $max_so_far;
}
// Function to find the maximum
// sum after given operations
function maxSum($a, $n)
{
// To store sum of all elements
$S = 0;
// Maximum sum of a subarray
$S1 = maxSubArraySum($a, $n);
// Calculate the sum of all elements
for ($i = 0; $i < $n; $i++)
$S += $a[$i];
return (2 * $S1 - $S);
}
// Driver Code
$a = array(-35, 32, -24, 0,
27, -10, 0, -19);
// size of an array
$n = sizeof($a);
echo( maxSum($a, $n));
// This code is contributed
// by Mukul Singh
Javascript
<script>
// javascript program to find the maximum
// sum after given operations
// Function to calculate Maximum Subarray Sum
// or Kadane's Algorithm
function maxSubArraySum(a , size)
{
var max_so_far = Number.MIN_VALUE, max_ending_here = 0;
for (i = 0; i < size; i++)
{
max_ending_here = max_ending_here + a[i];
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
if (max_ending_here < 0)
max_ending_here = 0;
}
return max_so_far;
}
// Function to find the maximum
// sum after given operations
function maxSum(a, n)
{
// To store sum of all elements
var S = 0;
// Maximum sum of a subarray
var S1 = maxSubArraySum(a, n);
// Calculate the sum of all elements
for (i = 0; i < n; i++)
S += a[i];
return (2 * S1 - S);
}
// Driver Code
var a = [ -35, 32, -24, 0, 27, -10, 0, -19 ];
// size of an array
var n = a.length;
document.write(maxSum(a, n));
// This code is contributed by todaysgaurav.
</script>
Producción:
99
Complejidad de tiempo: O(n), donde n representa el tamaño de la array dada.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.
Publicación traducida automáticamente
Artículo escrito por rupesh_rao y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA