Subarreglo de suma máxima eliminando como máximo un elemento

Dada una array, necesitamos encontrar el subarreglo de suma máxima, también se permite eliminar un elemento para obtener la suma máxima.

Ejemplos: 

Input  : arr[] = {1, 2, 3, -4, 5}
Output : 11
Explanation : We can get maximum sum subarray by
removing -4.

Input  : arr[] = [-2, -3, 4, -1, -2, 1, 5, -3]
Output : 9
Explanation : We can get maximum sum subarray by
removing -2 as, [4, -1, 1, 5] summing 9, which is 
the maximum achievable sum.

Si no se aplica la condición de eliminación de elementos, podemos resolver este problema usando el algoritmo de Kadane, pero aquí también se puede eliminar un elemento para aumentar la suma máxima. Esta condición se puede manejar usando dos arrays, array hacia adelante y hacia atrás, estas arrays almacenan la suma máxima actual del subarreglo desde el inicio hasta el i-ésimo índice, y desde el i-ésimo índice hasta el final, respectivamente. 

En el siguiente código, se escriben dos bucles, el primero almacena la suma de corriente máxima en dirección hacia adelante en fw[] y el otro bucle almacena lo mismo en dirección hacia atrás en bw[]. Obtener el máximo actual y la actualización es lo mismo que el algoritmo de Kadane. 

Ahora, cuando se crean ambos arreglos, podemos usarlos para las condiciones de eliminación de un elemento de la siguiente manera, en cada índice i, la suma máxima del subarreglo después de ignorar el i-ésimo elemento será fw[i-1] + bw[i+1] así que bucle para todos los valores i posibles y elegimos el máximo entre ellos. 

La complejidad temporal total y la complejidad espacial de la solución es O(N) 

Implementación:

// C++ program to get maximum sum subarray removing
// at-most one element
#include <bits/stdc++.h>
using namespace std;
 
// Method returns maximum sum of all subarray where
// removing one element is also allowed
int maxSumSubarrayRemovingOneEle(int arr[], int n)
{
    // Maximum sum subarrays in forward and backward
    // directions
    int fw[n], bw[n];
 
    // Initialize current max and max so far.
    int cur_max = arr[0], max_so_far = arr[0];
 
    // calculating maximum sum subarrays in forward
    // direction
    fw[0] = arr[0];
    for (int i = 1; i < n; i++)
    {
        cur_max = max(arr[i], cur_max + arr[i]);
        max_so_far = max(max_so_far, cur_max);
 
        // storing current maximum till ith, in
        // forward array
        fw[i] = cur_max;
    }
 
    // calculating maximum sum subarrays in backward
    // direction
    cur_max = max_so_far = bw[n-1] = arr[n-1];
    for (int i = n-2; i >= 0; i--)
    {
        cur_max = max(arr[i], cur_max + arr[i]);
        max_so_far = max(max_so_far, cur_max);
 
        // storing current maximum from ith, in
        // backward array
        bw[i] = cur_max;
    }
 
    /* Initializing final ans by max_so_far so that,
        case when no element is removed to get max sum
        subarray is also handled */
    int fans = max_so_far;
 
    // choosing maximum ignoring ith element
    for (int i = 1; i < n - 1; i++)
        fans = max(fans,max(0, fw[i - 1]) +max(0, bw[i + 1]));
  // In this condition we are checking when removing the ith element
  // so checking the max(0,left)+max(0,right), because maybe
  // left<0 || right<0 so it wont contribute to the answer
        if(fans==0){
          // if no positive element in array so return max_element
            return *max_element(arr,arr+n);
        }
    return fans;
 
}
 
// Driver code to test above methods
int main()
{
    int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << maxSumSubarrayRemovingOneEle(arr, n);
    return 0;
}

// Java program to get maximum sum subarray
// removing at-most one element
class GFG {
     
    // Method returns maximum sum of all subarray where
    // removing one element is also allowed
    static int maxSumSubarrayRemovingOneEle(int arr[],
                                                 int n)
    {
         
        // Maximum sum subarrays in forward and
        // backward directions
        int fw[] = new int[n];
        int bw[] = new int[n];
 
        // Initialize current max and max so far.
        int cur_max = arr[0], max_so_far = arr[0];
 
        // calculating maximum sum subarrays in forward
        // direction
        fw[0] = arr[0];
 
        for (int i = 1; i < n; i++) {
 
            cur_max = Math.max(arr[i], cur_max + arr[i]);
            max_so_far = Math.max(max_so_far, cur_max);
 
            // storing current maximum till ith, in
            // forward array
            fw[i] = cur_max;
        }
 
        // calculating maximum sum subarrays in backward
        // direction
        cur_max = max_so_far = bw[n - 1] = arr[n - 1];
         
        for (int i = n - 2; i >= 0; i--) {
 
            cur_max = Math.max(arr[i], cur_max + arr[i]);
            max_so_far = Math.max(max_so_far, cur_max);
 
            // storing current maximum from ith, in
            // backward array
            bw[i] = cur_max;
        }
 
        /* Initializing final ans by max_so_far so that,
        case when no element is removed to get max sum
        subarray is also handled */
        int fans = max_so_far;
 
        // choosing maximum ignoring ith element
        for (int i = 1; i < n - 1; i++)
            fans = Math.max(fans, fw[i - 1] + bw[i + 1]);
 
        return fans;
    }
     
    // Driver code
    public static void main(String arg[])
    {
        int arr[] = { -2, -3, 4, -1, -2, 1, 5, -3 };
        int n = arr.length;
         
        System.out.print(maxSumSubarrayRemovingOneEle(
                                             arr, n));
    }
}
 
// This code is contributed by Anant Agarwal.

# Python program to get maximum sum subarray removing
# at-most one element
 
# Method returns maximum sum of all subarray where
# removing one element is also allowed
def maxSumSubarrayRemovingOneEle(arr, n):
    # Maximum sum subarrays in forward and backward
    # directions
    fw = [0 for k in range(n)]
    bw = [0 for k in range(n)]
  
    # Initialize current max and max so far.
    cur_max, max_so_far = arr[0], arr[0]
    fw[0] = cur_max
  
    # calculating maximum sum subarrays in forward
    # direction
    for i in range(1,n):
        cur_max = max(arr[i], cur_max + arr[i])
        max_so_far = max(max_so_far, cur_max)
  
        # storing current maximum till ith, in
        # forward array
        fw[i] = cur_max
  
    # calculating maximum sum subarrays in backward
    # direction
    cur_max = max_so_far = bw[n-1] = arr[n-1]
    i = n-2
    while i >= 0:
        cur_max = max(arr[i], cur_max + arr[i])
        max_so_far = max(max_so_far, cur_max)
  
        # storing current maximum from ith, in
        # backward array
        bw[i] = cur_max
        i -= 1
  
    #  Initializing final ans by max_so_far so that,
    #  case when no element is removed to get max sum
    #  subarray is also handled
    fans = max_so_far
  
    #  choosing maximum ignoring ith element
    for i in range(1,n-1):
        fans = max(fans, fw[i - 1] + bw[i + 1])
  
    return fans
  
#  Driver code to test above methods
arr = [-2, -3, 4, -1, -2, 1, 5, -3]
n = len(arr)
print (maxSumSubarrayRemovingOneEle(arr, n))
 
# Contributed by: Afzal_Saan

// C# program to get maximum sum subarray
// removing at-most one element
using System;
class GFG {
     
    // Method returns maximum sum of all subarray where
    // removing one element is also allowed
    static int maxSumSubarrayRemovingOneEle(int []arr,
                                                int n)
    {
         
        // Maximum sum subarrays in forward and
        // backward directions
        int []fw = new int[n];
        int []bw = new int[n];
 
        // Initialize current max and max so far.
        int cur_max = arr[0], max_so_far = arr[0];
 
        // calculating maximum sum subarrays in forward
        // direction
        fw[0] = arr[0];
 
        for (int i = 1; i < n; i++) {
 
            cur_max = Math.Max(arr[i], cur_max + arr[i]);
            max_so_far = Math.Max(max_so_far, cur_max);
 
            // storing current maximum till ith, in
            // forward array
            fw[i] = cur_max;
        }
 
        // calculating maximum sum subarrays in backward
        // direction
        cur_max = max_so_far = bw[n - 1] = arr[n - 1];
         
        for (int i = n - 2; i >= 0; i--) {
 
            cur_max = Math.Max(arr[i], cur_max + arr[i]);
            max_so_far = Math.Max(max_so_far, cur_max);
 
            // storing current maximum from ith, in
            // backward array
            bw[i] = cur_max;
        }
 
        /* Initializing final ans by max_so_far so that,
        case when no element is removed to get max sum
        subarray is also handled */
        int fans = max_so_far;
 
        // choosing maximum ignoring ith element
        for (int i = 1; i < n - 1; i++)
            fans = Math.Max(fans, fw[i - 1] + bw[i + 1]);
 
        return fans;
    }
     
    // Driver code
    public static void Main()
    {
        int []arr = { -2, -3, 4, -1, -2, 1, 5, -3 };
        int n = arr.Length;
         
        Console.WriteLine(maxSumSubarrayRemovingOneEle(
                                            arr, n));
    }
}
 
// This code is contributed by anuj_67.

<?php
// PHP program to get maximum
// sum subarray removing
// at-most one element
 
// Method returns maximum sum
// of all subarray where removing
// one element is also allowed
function maxSumSubarrayRemovingOneEle( $arr, $n)
{
    // Maximum sum subarrays in
    // forward and backward directions
    $fw = array(); $bw = array();
 
    // Initialize current
    // max and max so far.
    $cur_max = $arr[0];
    $max_so_far = $arr[0];
 
    // calculating maximum sum
    // subarrays in forward direction
    $fw[0] = $arr[0];
    for ($i = 1; $i < $n; $i++)
    {
        $cur_max = max($arr[$i],
                       $cur_max + $arr[$i]);
        $max_so_far = max($max_so_far,
                          $cur_max);
 
        // storing current maximum till
        // ith, in forward array
        $fw[$i] = $cur_max;
    }
 
    // calculating maximum sum
    // subarrays in backward direction
    $cur_max = $max_so_far =
    $bw[$n - 1] = $arr[$n - 1];
    for ( $i = $n - 2; $i >= 0; $i--)
    {
        $cur_max = max($arr[$i],
                       $cur_max + $arr[$i]);
        $max_so_far = max($max_so_far,
                          $cur_max);
 
        // storing current maximum from
        // ith, in backward array
        $bw[$i] = $cur_max;
    }
 
    /* Initializing final ans by
        max_so_far so that, case
        when no element is removed
        to get max sum subarray is
        also handled */
    $fans = $max_so_far;
 
    // choosing maximum
    // ignoring ith element
    for ($i = 1; $i < $n - 1; $i++)
        $fans = max($fans, $fw[$i - 1] +
                           $bw[$i + 1]);
 
    return $fans;
}
 
// Driver Code
$arr = array(-2, -3, 4, -1,
             -2, 1, 5, -3);
$n = count($arr);
echo maxSumSubarrayRemovingOneEle($arr, $n);
 
// This code is contributed by anuj_67.
?>

<script>
 
// JavaScript program to get maximum sum subarray
// removing at-most one element
  
// Method returns maximum sum of all subarray where
// removing one element is also allowed
function maxSumSubarrayRemovingOneEle(arr, n)
{
     
    // Maximum sum subarrays in forward and
    // backward directions
    let fw = [];
    let bw = [];
 
    // Initialize current max and max so far.
    let cur_max = arr[0], max_so_far = arr[0];
 
    // calculating maximum sum subarrays in forward
    // direction
    fw[0] = arr[0];
 
    for(let i = 1; i < n; i++)
    {
        cur_max = Math.max(arr[i], cur_max + arr[i]);
        max_so_far = Math.max(max_so_far, cur_max);
 
        // Storing current maximum till ith,
        // in forward array
        fw[i] = cur_max;
    }
 
    // Calculating maximum sum subarrays
    // in backward direction
    cur_max = max_so_far = bw[n - 1] = arr[n - 1];
       
    for(let i = n - 2; i >= 0; i--)
    {
        cur_max = Math.max(arr[i], cur_max + arr[i]);
        max_so_far = Math.max(max_so_far, cur_max);
 
        // Storing current maximum from ith, in
        // backward array
        bw[i] = cur_max;
    }
 
    /* Initializing final ans by max_so_far so that,
    case when no element is removed to get max sum
    subarray is also handled */
    let fans = max_so_far;
 
    // Choosing maximum ignoring ith element
    for(let i = 1; i < n - 1; i++)
        fans = Math.max(fans, fw[i - 1] +
                              bw[i + 1]);
 
    return fans;
}
 
// Driver Code
let arr = [ -2, -3, 4, -1, -2, 1, 5, -3 ];
let n = arr.length;
       
document.write(
    maxSumSubarrayRemovingOneEle(arr, n));
   
</script>

Producción : 

9

Tiempo Complejidad : O(n) 
Espacio Auxiliar : O(n)

Este artículo es una contribución de Vinish Thanai. Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.