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++
// 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
// 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.
Python3
# 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#
// 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
// 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.
?>
Javascript
<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.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA