Maximice la suma de un Array cambiando el signo de todos los elementos de un único subarreglo

Dada una array arr[] de N enteros, la tarea es encontrar la suma máxima de la array que se puede obtener cambiando los signos de cualquier subarreglo de la array dada como máximo una vez.

Ejemplos:

Entrada: arr[] = {-2, 3, -1, -4, -2} 
Salida: 8
Explicación: 
Cambiar los signos del subarreglo {-1, -4, -2} modifica el arreglo a {-2, 3 , 1, 4, 2}. Por lo tanto, la suma del arreglo = -2 + 3 + 1 + 4 + 2 = 8, que es el máximo posible.

Entrada: arr[] = {1, 2, -10, 2, -20}
Salida: 31 
Explicación: 
Cambiar los signos del subarreglo {-10, 2, -20} modifica el arreglo a {1, 2, 10, – 2, 20}. Por lo tanto, la suma del arreglo = 1 + 2 + 10 – 2 + 20 = 31, que es el máximo posible.

Enfoque ingenuo: el enfoque más simple es calcular la suma total de la array y luego generar todos los subarreglos posibles . Ahora, para cada subarreglo { A[i], … A[j] }, reste su suma, sum(A[i], …, A[j]) , de la suma total y cambie los signos de los elementos del subarreglo. Después de voltear el subarreglo, agregue la suma del subarreglo volteado, es decir, (-1 * sum(A[i], …, A[j])) , a la suma total. A continuación se muestran los pasos:

1. Encuentre la suma total de la array original (por ejemplo, total_sum ) y guárdela.
2. Ahora, para todos los subarreglos posibles, encuentre el máximo de total_sum – 2 * sum(i, j) .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum sum
// after flipping a subarray
int maxSumFlip(int a[], int n)
{
 
    // Stores the total sum of array
    int total_sum = 0;
    for (int i = 0; i < n; i++)
        total_sum += a[i];
 
    // Initialize the maximum sum
    int max_sum = INT_MIN;
 
    // Iterate over all possible subarrays
    for (int i = 0; i < n; i++)
    {
        // Initialize sum of the subarray
        // before flipping sign
        int sum = 0;
 
        for (int j = i; j < n; j++)
        {
            // Calculate the sum of
            // original subarray
            sum += a[j];
 
            // Subtract the original
            // subarray sum and add
            // the flipped subarray
            // sum to the total sum
            max_sum = max(max_sum, total_sum - 2 * sum);
        }
    }
 
    // Return the max_sum
    return max(max_sum, total_sum);
}
 
// Driver Code
int main()
{
    int arr[] = { -2, 3, -1, -4, -2 };
    int N = sizeof(arr) / sizeof(int);
 
    cout << maxSumFlip(arr, N);
}
 
// This code is contributed by sanjoy_62

// Java program for the above approach
 
import java.io.*;
 
public class GFG
{
    // Function to find the maximum sum
    // after flipping a subarray
    public static int maxSumFlip(int a[], int n)
    {
        // Stores the total sum of array
        int total_sum = 0;
        for (int i = 0; i < n; i++)
            total_sum += a[i];
 
        // Initialize the maximum sum
        int max_sum = Integer.MIN_VALUE;
 
        // Iterate over all possible subarrays
        for (int i = 0; i < n; i++)
        {
            // Initialize sum of the subarray
            // before flipping sign
            int sum = 0;
 
            for (int j = i; j < n; j++)
            {
                // Calculate the sum of
                // original subarray
                sum += a[j];
 
                // Subtract the original
                // subarray sum and add
                // the flipped subarray
                // sum to the total sum
                max_sum = Math.max(max_sum,
                                   total_sum - 2 * sum);
            }
        }
 
        // Return the max_sum
        return Math.max(max_sum, total_sum);
    }
 
    // Driver Code
    public static void main(String args[])
    {
        int arr[] = { -2, 3, -1, -4, -2 };
        int N = arr.length;
       
        // Function call
        System.out.println(maxSumFlip(arr, N));
    }
}

# Python3 program for the above approach
import sys
 
# Function to find the maximum sum
# after flipping a subarray
 
 
def maxSumFlip(a, n):
 
    # Stores the total sum of array
    total_sum = 0
    for i in range(n):
        total_sum += a[i]
 
    # Initialize the maximum sum
    max_sum = -sys.maxsize - 1
 
    # Iterate over all possible subarrays
    for i in range(n):
 
        # Initialize sum of the subarray
        # before flipping sign
        sum = 0
 
        for j in range(i, n):
 
            # Calculate the sum of
            # original subarray
            sum += a[j]
 
            # Subtract the original
            # subarray sum and add
            # the flipped subarray
            # sum to the total sum
            max_sum = max(max_sum,
                          total_sum - 2 * sum)
 
    # Return the max_sum
    return max(max_sum, total_sum)
 
 
# Driver Code
arr = [-2, 3, -1, -4, -2]
N = len(arr)
 
print(maxSumFlip(arr, N))
 
# This code is contributed by sanjoy_62

// C# program for the above approach
using System;
class GFG {
 
    // Function to find the maximum sum
    // after flipping a subarray
    public static int maxSumFlip(int[] a, int n)
    {
 
        // Stores the total sum of array
        int total_sum = 0;
        for (int i = 0; i < n; i++)
            total_sum += a[i];
 
        // Initialize the maximum sum
        int max_sum = int.MinValue;
 
        // Iterate over all possible subarrays
        for (int i = 0; i < n; i++)
        {
            // Initialize sum of the subarray
            // before flipping sign
            int sum = 0;
 
            for (int j = i; j < n; j++)
            {
                // Calculate the sum of
                // original subarray
                sum += a[j];
 
                // Subtract the original
                // subarray sum and add
                // the flipped subarray
                // sum to the total sum
                max_sum = Math.Max(max_sum,
                                   total_sum - 2 * sum);
            }
        }
 
        // Return the max_sum
        return Math.Max(max_sum, total_sum);
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        int[] arr = { -2, 3, -1, -4, -2 };
        int N = arr.Length;
 
        // Function call
        Console.WriteLine(maxSumFlip(arr, N));
    }
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javascript program to implement
// the above approach
 
    // Function to find the maximum sum
    // after flipping a subarray
    function maxSumFlip(a, n)
    {
        // Find the total sum of array
        let total_sum = 0;
        for (let i = 0; i < n; i++)
            total_sum += a[i];
  
        // Using Kadane's Algorithm
        let max_ending_here = -a[0] - a[0];
        let curr_sum = -a[0] - a[0];
  
        for (let i = 1; i < n; i++)
        {
            // Either extend previous
            // sub_array or start
            // new subarray
            curr_sum = Math.max(curr_sum + (-a[i] - a[i]),
                                (-a[i] - a[i]));
  
            // Keep track of max_sum array
            max_ending_here
                = Math.max(max_ending_here, curr_sum);
        }
  
        // Add the sum to the total_sum
        let max_sum = total_sum + max_ending_here;
  
        // Check max_sum was maximum
        // with flip or without flip
        max_sum = Math.max(max_sum, total_sum);
  
        // Return max_sum
        return max_sum;
    }
  
 
// Driver Code
 
        let arr = [ -2, 3, -1, -4, -2 ];
        let N = arr.length;
  
        // Function Call
        document.write(maxSumFlip(arr, N));
                 
</script>

8

Complejidad de Tiempo: O(N ² ) 
Espacio Auxiliar: O(1)

Enfoque eficiente: a partir del enfoque anterior, se puede observar que, para obtener la suma máxima de arrays, (2 * suma de subarreglos) debe maximizarse para todos los subarreglos. Esto se puede hacer usando Programación Dinámica . A continuación se muestran los pasos:

1. Encuentre el subarreglo de suma mínima de l[] usando el algoritmo de Kadane
2. Esto maximiza la contribución de (2 * sum) sobre todos los subarreglos.
3. Agregue la contribución máxima a la suma total de la array.

A continuación se muestra la implementación del enfoque anterior:

#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum sum
// after flipping a subarray
int maxSumFlip(int a[], int n)
{
 
    // Stores the total sum of array
    int total_sum = 0;
    for (int i = 0; i < n; i++)
        total_sum += a[i];
 
      // Kadane's algorithm to find the minimum subarray sum
    int b=0,temp=2e9;
    for (int i = 0; i < n; i++)
    {
          b+=a[i];
          if(temp>b)
          temp=b;
          if(b>0)
          b=0;
    }
 
    // Return the max_sum
    return max(total_sum,total_sum-2*temp);
}
 
// Driver Code
int main()
{
    int arr[] = { -2, 3, -1, -4, -2 };
    int N = sizeof(arr) / sizeof(int);
 
    cout << maxSumFlip(arr, N);
}

import java.util.*;
import java.io.*;
 
// Java program for the above approach
class GFG{
 
  // Function to find the maximum sum
  // after flipping a subarray
  static int maxSumFlip(int ar[], int n)
  {
 
    // Stores the total sum of array
    int total_sum = 0;
    for (int i = 0 ; i < n ; i++){
      total_sum += ar[i];
    }
 
    // Kadane's algorithm to find the minimum subarray sum
    int b = 0;
    int a = 2000000000;
    for (int i = 0 ; i < n ; i++)
    {
      b += ar[i];
      if(a > b){
        a = b;
      }
      if(b > 0){
        b = 0;
      }
    }
 
    // Return the max_sum
    return Math.max(total_sum, total_sum - 2*a);
  }
 
  // Driver Code
  public static void main(String args[])
  {
    int arr[] = new int[]{ -2, 3, -1, -4, -2 };
    int N = arr.length;
 
    System.out.println(maxSumFlip(arr, N));
  }
}
 
// This code is contributed by entertain2022.

def maxsum(l,n):
  total_sum=sum(l)
  #kadane's algorithm to find the minimum subarray sum
  current_sum=0
  minimum_sum=0
  for i in l:
    current_sum+=i
    minimum_sum=min(minimum_sum,current_sum)
    current_sum=min(current_sum,0)
  return max(total_sum,total_sum-2*minimum_sum)
l=[-2,3,-1,-4,-2]
n=len(l)
print(maxsum(l,n))

<script>
 
function maxsum(l,n){
let total_sum = 0;
for (let i = 0; i < n; i++)
   total_sum += l[i];
    
// kadane's algorithm to find the minimum subarray sum
let current_sum=0
let minimum_sum=0
for(let i of l){
    current_sum += i
    minimum_sum = Math.min(minimum_sum,current_sum)
    current_sum = Math.min(current_sum,0)
}
return Math.max(total_sum, total_sum-2*minimum_sum)
}
 
// driver code
let l = [-2, 3, -1, -4, -2]
let n = l.length
document.write(maxsum(l,n))
 
// This code is contributed by shinjanpatra
 
</script>

8

Complejidad de tiempo: O(N) 
Espacio auxiliar: O(1)
Nota: También se puede hacer encontrando la suma mínima del subarreglo e imprimiendo max(TotalSum, TotalSum-2*(minsubarraysum))