Maximice la suma máxima de subarreglo después de eliminar al menos un elemento

Posted on by Rudeus Greyrat

Dada una array arr[] de N enteros. La tarea es encontrar primero la suma máxima del subconjunto y luego eliminar como máximo un elemento del subconjunto. Si hay varios subconjuntos con la suma máxima de subconjuntos, elimine como máximo un solo elemento de modo que la suma máxima después de la eliminación se maximice. La tarea es maximizar la suma obtenida después de la eliminación.
Nota: primero debe encontrar la suma máxima del subconjunto y luego eliminar el elemento de ese subconjunto si es necesario. Además, después de la eliminación, el tamaño del subconjunto debe ser al menos 1.
Ejemplos: 
 

Entrada: arr[] = {1, 2, 3, -2, 3} 
Salida: 9 
La suma máxima del subconjunto viene dada por el subconjunto {2, 3, -2, 3} 
Por lo tanto, podemos eliminar – 2 para maximizar aún más la suma del subarreglo. 
Entrada: arr[] = {-1, -2} 
Salida: -1 
La suma máxima del subconjunto proviene del subconjunto {-1} y no es necesario eliminarlo. 
 

Enfoque : use el algoritmo de Kadane para encontrar la suma máxima del subarreglo. Una vez que se haya encontrado la suma, vuelva a aplicar el algoritmo de Kadane para encontrar la suma máxima nuevamente con algunos cambios menores. Use dos variables adicionales en el bucle, cnt y mini . La variable cnt cuenta el número de elementos en el subconjunto y mini almacena el valor mínimo en todos los subconjuntos que tienen la misma suma que el subconjunto máximo. Si el elemento mínimo así obtenido es menor que 0 , entonces solo eliminamos un elemento del subarreglo, o de lo contrario no lo hacemos. 
A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the maximum sub-array sum
int maxSubArraySum(int a[], int size)
{
 
    // Initialized
    int max_so_far = INT_MIN, max_ending_here = 0;
 
    // Traverse in the array
    for (int i = 0; i < size; i++) {
 
        // Increase the sum
        max_ending_here = max_ending_here + a[i];
 
        // If sub-array sum is more than the previous
        if (max_so_far < max_ending_here)
            max_so_far = max_ending_here;
 
        // If sum is negative
        if (max_ending_here < 0)
            max_ending_here = 0;
    }
    return max_so_far;
}
 
// Function that returns the maximum sub-array sum
// after removing an element from the same sub-array
int maximizeSum(int a[], int n)
{
    int cnt = 0;
    int mini = INT_MAX;
    int minSubarray = INT_MAX;
 
    // Maximum sub-array sum using Kadane's Algorithm
    int sum = maxSubArraySum(a, n);
 
    int max_so_far = INT_MIN, max_ending_here = 0;
 
    // Re-apply Kadane's with minor changes
    for (int i = 0; i < n; i++) {
 
        // Increase the sum
        max_ending_here = max_ending_here + a[i];
        cnt++;
        minSubarray = min(a[i], minSubarray);
 
        // If sub-array sum is greater than the previous
        if (sum == max_ending_here) {
 
            // If elements are 0, no removal
            if (cnt == 1)
                mini = min(mini, 0);
 
            // If elements are more, then store
            // the minimum value in the sub-array
            // obtained till now
            else
                mini = min(mini, minSubarray);
        }
 
        // If sum is negative
        if (max_ending_here < 0) {
 
            // Re-initialize everything
            max_ending_here = 0;
            cnt = 0;
            minSubarray = INT_MAX;
        }
    }
 
    return sum - mini;
}
 
// Driver code
int main()
{
    int a[] = { 1, 2, 3, -2, 3 };
    int n = sizeof(a) / sizeof(a[0]);
    cout << maximizeSum(a, n);
 
    return 0;
}

Java

// Java implementation of the approach
class GFG
{
     
// Function to return the maximum sub-array sum
static int maxSubArraySum(int a[], int size)
{
 
    // Initialized
    int max_so_far = Integer.MIN_VALUE,
        max_ending_here = 0;
 
    // Traverse in the array
    for (int i = 0; i < size; i++)
    {
 
        // Increase the sum
        max_ending_here = max_ending_here + a[i];
 
        // If sub-array sum is more than the previous
        if (max_so_far < max_ending_here)
            max_so_far = max_ending_here;
 
        // If sum is negative
        if (max_ending_here < 0)
            max_ending_here = 0;
    }
    return max_so_far;
}
 
// Function that returns the maximum sub-array sum
// after removing an element from the same sub-array
static int maximizeSum(int a[], int n)
{
    int cnt = 0;
    int mini = Integer.MAX_VALUE;
    int minSubarray = Integer.MAX_VALUE;
 
    // Maximum sub-array sum
    // using Kadane's Algorithm
    int sum = maxSubArraySum(a, n);
 
    int max_so_far = Integer.MIN_VALUE,
        max_ending_here = 0;
 
    // Re-apply Kadane's with minor changes
    for (int i = 0; i < n; i++)
    {
 
        // Increase the sum
        max_ending_here = max_ending_here + a[i];
        cnt++;
        minSubarray = Math.min(a[i], minSubarray);
 
        // If sub-array sum is greater than the previous
        if (sum == max_ending_here)
        {
 
            // If elements are 0, no removal
            if (cnt == 1)
                mini = Math.min(mini, 0);
 
            // If elements are more, then store
            // the minimum value in the sub-array
            // obtained till now
            else
                mini = Math.min(mini, minSubarray);
        }
 
        // If sum is negative
        if (max_ending_here < 0)
        {
 
            // Re-initialize everything
            max_ending_here = 0;
            cnt = 0;
            minSubarray = Integer.MAX_VALUE;
        }
    }
 
    return sum - mini;
}
 
// Driver code
public static void main(String[] args)
{
    int a[] = { 1, 2, 3, -2, 3 };
    int n = a.length;
    System.out.println(maximizeSum(a, n));
}
}
 
// This code is contributed by Code_Mech

Python3

# Python3 implementation of the approach
import sys;
 
# Function to return the maximum sub-array sum
def maxSubArraySum(a, size) :
 
    # Initialized
    max_so_far = -(sys.maxsize - 1);
    max_ending_here = 0;
 
    # Traverse in the array
    for i in range(size) :
 
        # Increase the sum
        max_ending_here = max_ending_here + a[i];
 
        # If sub-array sum is more than the previous
        if (max_so_far < max_ending_here) :
            max_so_far = max_ending_here;
 
        # If sum is negative
        if (max_ending_here < 0) :
            max_ending_here = 0;
     
    return max_so_far;
 
# Function that returns the maximum
# sub-array sum after removing an
# element from the same sub-array
def maximizeSum(a, n) :
 
    cnt = 0;
    mini = sys.maxsize;
    minSubarray = sys.maxsize;
 
    # Maximum sub-array sum using
    # Kadane's Algorithm
    sum = maxSubArraySum(a, n);
 
    max_so_far = -(sys.maxsize - 1);
    max_ending_here = 0;
 
    # Re-apply Kadane's with minor changes
    for i in range(n) :
 
        # Increase the sum
        max_ending_here = max_ending_here + a[i];
        cnt += 1;
        minSubarray = min(a[i], minSubarray);
 
        # If sub-array sum is greater
        # than the previous
        if (sum == max_ending_here) :
 
            # If elements are 0, no removal
            if (cnt == 1) :
                mini = min(mini, 0);
 
            # If elements are more, then store
            # the minimum value in the sub-array
            # obtained till now
            else :
                mini = min(mini, minSubarray);
         
        # If sum is negative
        if (max_ending_here < 0) :
 
            # Re-initialize everything
            max_ending_here = 0;
            cnt = 0;
            minSubarray = sys.maxsize;
 
    return sum - mini;
 
# Driver code
if __name__ == "__main__" :
 
    a = [ 1, 2, 3, -2, 3 ];
    n = len(a)
     
    print(maximizeSum(a, n));
 
# This code is contributed by Ryuga

C#

// C# implementation of the approach
using System;
 
class GFG
{
     
// Function to return the maximum sub-array sum
static int maxSubArraySum(int []a, int size)
{
 
    // Initialized
    int max_so_far = int.MinValue,
        max_ending_here = 0;
 
    // Traverse in the array
    for (int i = 0; i < size; i++)
    {
 
        // Increase the sum
        max_ending_here = max_ending_here + a[i];
 
        // If sub-array sum is more than the previous
        if (max_so_far < max_ending_here)
            max_so_far = max_ending_here;
 
        // If sum is negative
        if (max_ending_here < 0)
            max_ending_here = 0;
    }
    return max_so_far;
}
 
// Function that returns the maximum sub-array sum
// after removing an element from the same sub-array
static int maximizeSum(int []a, int n)
{
    int cnt = 0;
    int mini = int.MaxValue;
    int minSubarray = int.MaxValue;
 
    // Maximum sub-array sum
    // using Kadane's Algorithm
    int sum = maxSubArraySum(a, n);
 
    int max_so_far = int.MinValue,
        max_ending_here = 0;
 
    // Re-apply Kadane's with minor changes
    for (int i = 0; i < n; i++)
    {
 
        // Increase the sum
        max_ending_here = max_ending_here + a[i];
        cnt++;
        minSubarray = Math.Min(a[i], minSubarray);
 
        // If sub-array sum is greater than the previous
        if (sum == max_ending_here)
        {
 
            // If elements are 0, no removal
            if (cnt == 1)
                mini = Math.Min(mini, 0);
 
            // If elements are more, then store
            // the minimum value in the sub-array
            // obtained till now
            else
                mini = Math.Min(mini, minSubarray);
        }
 
        // If sum is negative
        if (max_ending_here < 0)
        {
 
            // Re-initialize everything
            max_ending_here = 0;
            cnt = 0;
            minSubarray = int.MaxValue;
        }
    }
 
    return sum - mini;
}
 
// Driver code
public static void Main(String[] args)
{
    int []a = { 1, 2, 3, -2, 3 };
    int n = a.Length;
    Console.WriteLine(maximizeSum(a, n));
}
}
 
// This code has been contributed by 29AjayKumar

PHP

<?php
// PHP implementation of the approach
 
// Function to return the maximum sub-array sum
function maxSubArraySum($a, $size)
{
 
    // Initialized
    $max_so_far = PHP_INT_MIN;
    $max_ending_here = 0;
 
    // Traverse in the array
    for ( $i = 0; $i < $size; $i++)
    {
 
        // Increase the sum
        $max_ending_here = $max_ending_here + $a[$i];
 
        // If sub-array sum is more than the previous
        if ($max_so_far < $max_ending_here)
            $max_so_far = $max_ending_here;
 
        // If sum is negative
        if ($max_ending_here < 0)
            $max_ending_here = 0;
    }
    return $max_so_far;
}
 
// Function that returns the maximum sub-array sum
// after removing an element from the same sub-array
function maximizeSum($a, $n)
{
    $cnt = 0;
    $mini = PHP_INT_MAX;
    $minSubarray = PHP_INT_MAX;
 
    // Maximum sub-array sum using Kadane's Algorithm
    $sum = maxSubArraySum($a, $n);
 
    $max_so_far = PHP_INT_MIN;
    $max_ending_here = 0;
 
    // Re-apply Kadane's with minor changes
    for ($i = 0; $i < $n; $i++)
    {
 
        // Increase the sum
        $max_ending_here = $max_ending_here + $a[$i];
        $cnt++;
        $minSubarray = min($a[$i], $minSubarray);
 
        // If sub-array sum is greater than the previous
        if ($sum == $max_ending_here)
        {
 
            // If elements are 0, no removal
            if ($cnt == 1)
                $mini = min($mini, 0);
 
            // If elements are more, then store
            // the minimum value in the sub-array
            // obtained till now
            else
                $mini = min($mini, $minSubarray);
        }
 
        // If sum is negative
        if ($max_ending_here < 0)
        {
 
            // Re-initialize everything
            $max_ending_here = 0;
            $cnt = 0;
            $minSubarray = PHP_INT_MAX;
        }
    }
    return $sum - $mini;
}
 
    // Driver code
    $a = array( 1, 2, 3, -2, 3 );
    $n = sizeof($a) / sizeof($a[0]);
    echo maximizeSum($a, $n);
 
// This code is contributed by Tushil.
?>

Javascript

<script>
// Java script implementation of the approach
 
// Function to return the maximum sub-array sum
function maxSubArraySum(a,size)
{
 
    // Initialized
    let max_so_far = Number.MIN_VALUE,
        max_ending_here = 0;
 
    // Traverse in the array
    for (let i = 0; i < size; i++)
    {
 
        // Increase the sum
        max_ending_here = max_ending_here + a[i];
 
        // If sub-array sum is more than the previous
        if (max_so_far < max_ending_here)
            max_so_far = max_ending_here;
 
        // If sum is negative
        if (max_ending_here < 0)
            max_ending_here = 0;
    }
    return max_so_far;
}
 
// Function that returns the maximum sub-array sum
// after removing an element from the same sub-array
function maximizeSum(a,n)
{
    let cnt = 0;
    let mini = Number.MAX_VALUE;
    let minSubarray = Number.MAX_VALUE;
 
    // Maximum sub-array sum
    // using Kadane's Algorithm
    let sum = maxSubArraySum(a, n);
 
    let max_so_far = Number.MIN_VALUE,
        max_ending_here = 0;
 
    // Re-apply Kadane's with minor changes
    for (let i = 0; i < n; i++)
    {
 
        // Increase the sum
        max_ending_here = max_ending_here + a[i];
        cnt++;
        minSubarray = Math.min(a[i], minSubarray);
 
        // If sub-array sum is greater than the previous
        if (sum == max_ending_here)
        {
 
            // If elements are 0, no removal
            if (cnt == 1)
                mini = Math.min(mini, 0);
 
            // If elements are more, then store
            // the minimum value in the sub-array
            // obtained till now
            else
                mini = Math.min(mini, minSubarray);
        }
 
        // If sum is negative
        if (max_ending_here < 0)
        {
 
            // Re-initialize everything
            max_ending_here = 0;
            cnt = 0;
            minSubarray = Integer.MAX_VALUE;
        }
    }
 
    return sum - mini;
}
 
// Driver code
 
    let a = [ 1, 2, 3, -2, 3 ];
    let n = a.length;
    document.write(maximizeSum(a, n));
 
 
// This code is contributed by sravan kumar Gottumukkala
</script>
Producción: 

9

 

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por Striver y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *