Suma máxima de subarreglo posible después de eliminar como máximo un subarreglo

Dada una array arr[] que consta de N enteros, la tarea es encontrar la suma máxima de cualquier subarreglo posible después de eliminar como máximo un subarreglo de la array dada.

Ejemplos:

Entrada: arr[] = {-1, 5, 2, -1, 6}
Salida: 13
Explicación:
La suma máxima se puede obtener seleccionando el subarreglo {5, 2, -1, 6} y eliminando el subarreglo {- 1}.

Entrada: arr[] = {7, 6, -1, -4, -5, 7, 1, -2, -3}
Salida: 21

Enfoque: Siga los pasos para resolver el problema:

  • Encuentre el índice de la izquierda ( l ) y la derecha ( r ) número más + cinco en la array
  • Si hay +ve números, calcule la suma del índice l a r
    • de lo contrario, devuelva la suma máxima de la subarray (calcule usando el algoritmo de Kadane).
  • Ahora, calcule la suma mínima del subarreglo (minSubArrSum) para el rango arr[lr] usando el algoritmo de Kadane
  • Si minSubArrSum < 0 entonces el resultado = sum-minSubArrSum
    • otro resultado = suma

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

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
int kadaneMinSubArr(int* nums, int l, int r);
int kadaneMaxSubArr(int* nums, int l, int r);
 
void maxSubArrSum(int* nums, int n)
{
    // !T(N) = O(n)
    // !S(N) = O(1)
    // finding the left most positive elements and right
    // most positive elements indexes
    int l = -1, r = -1, sum = 0, minSubSum;
 
    // left most positive element
    for (int i = 0; i < n; i++) {
        if (nums[i] >= 0) {
            l = i;
            break;
        }
    }
 
    // right most positive element
    for (int i = n - 1; i >= 0; i--) {
        if (nums[i] >= 0) {
            r = i;
            break;
        }
    }
 
    if (l == -1 && r == -1) {
        // all are -ve numbers
        // maximum sum of subarray
        cout << kadaneMaxSubArr(nums, 0, n - 1);
        return;
    }
    // finding sum
    for (int i = l; i <= r; i++)
        sum += nums[i];
 
    // minimum sum of subarray
    minSubSum = kadaneMinSubArr(nums, l, r);
    cout << ((minSubSum < 0) ? sum - minSubSum : sum);
}
 
int kadaneMaxSubArr(int* nums, int l, int r)
{
    // l : left-bound index
    // r : right-bound index
 
    // !T(N) = O(N)
    // !S(N) = O(1)
 
    // finding the maxSubArrSum
    int sum = nums[l], maxSum = nums[l];
 
    for (int i = l; i <= r; i++) {
        sum = max(sum + nums[i], nums[i]);
        maxSum = max(maxSum, sum);
    }
 
    return maxSum;
}
 
int kadaneMinSubArr(int* nums, int l, int r)
{
    // !T(N) = O(N)
    // !S(N) = O(1)
    // finding the minSubArrSum
    int sum = nums[l], minSum = nums[l];
    for (int i = l; i <= r; i++) {
        sum = min(sum + nums[i], nums[i]);
        minSum = min(minSum, sum);
    }
 
    return minSum;
}
 
// Driver Code
int main()
{
    int arr[] = { 7, 6, -1, -4, -5, 7, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    maxSubArrSum(arr, n);
 
    return 0;
}
 
// This code is contributed by jaladisishir96

C

// C program for the above approach
#include <stdio.h>
 
int kadaneMinSubArr(int* nums, int l, int r);
int kadaneMaxSubArr(int* nums, int l, int r);
 
// Find maximum between two numbers.
int max(int num1, int num2)
{
    return (num1 > num2) ? num1 : num2;
}
 
// Find minimum between two numbers.
int min(int num1, int num2)
{
    return (num1 > num2) ? num2 : num1;
}
 
void maxSubArrSum(int* nums, int n)
{
    // !T(N) = O(n)
    // !S(N) = O(1)
    // finding the left most positive elements and right
    // most positive elements indexes
    int l = -1, r = -1, sum = 0, minSubSum;
 
    // left most positive element
    for (int i = 0; i < n; i++) {
        if (nums[i] >= 0) {
            l = i;
            break;
        }
    }
 
    // right most positive element
    for (int i = n - 1; i >= 0; i--) {
        if (nums[i] >= 0) {
            r = i;
            break;
        }
    }
 
    if (l == -1 && r == -1) {
        // all are -ve numbers
        // maximum sum of subarray
        printf("%d", kadaneMaxSubArr(nums, 0, n - 1));
        return;
    }
    // finding sum
    for (int i = l; i <= r; i++)
        sum += nums[i];
    // minimum sum of subarray
    minSubSum = kadaneMinSubArr(nums, l, r);
    (minSubSum < 0) ? printf("%d", sum - minSubSum)
                    : printf("%d", sum);
}
 
int kadaneMaxSubArr(int* nums, int l, int r)
{
    // l : left-bound index
    // r : right-bound index
 
    // !T(N) = O(N)
    // !S(N) = O(1)
 
    // finding the maxSubArrSum
    int sum = nums[l], maxSum = nums[l];
 
    for (int i = l; i <= r; i++) {
        sum = max(sum + nums[i], nums[i]);
        maxSum = max(maxSum, sum);
    }
 
    return maxSum;
}
 
int kadaneMinSubArr(int* nums, int l, int r)
{
    // !T(N) = O(N)
    // !S(N) = O(1)
    // finding the minSubArrSum
    int sum = nums[l], minSum = nums[l];
    for (int i = l; i <= r; i++) {
        sum = min(sum + nums[i], nums[i]);
        minSum = min(minSum, sum);
    }
 
    return minSum;
}
 
// Driver Code
int main()
{
    int arr[] = { 7, 6, -1, -4, -5, 7, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    maxSubArrSum(arr, n);
 
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta

Java

// Java program for the above approach
import java.io.*;
import java.util.*;
 
class GFG {
 
    // Function to find maximum
    // subarray sum possible after
    // removing at most one subarray
    public static void maximumSum(
        int arr[], int n)
    {
        long[] preSum = new long[n];
 
        long sum = 0;
        long maxSum = 0;
 
        // Calculate the preSum[] array
        for (int i = 0; i < n; i++) {
 
            // Update the value of sum
            sum = Math.max(arr[i],
                           sum + arr[i]);
 
            // Update the value of maxSum
            maxSum = Math.max(maxSum,
                              sum);
 
            // Update the value of preSum[i]
            preSum[i] = maxSum;
        }
 
        sum = 0;
        maxSum = 0;
 
        long[] postSum = new long[n + 1];
 
        // Calculate the postSum[] array
        for (int i = n - 1; i >= 0; i--) {
 
            // Update the value of sum
            sum = Math.max(arr[i],
                           sum + arr[i]);
 
            // Update the value of maxSum
            maxSum = Math.max(maxSum,
                              sum);
 
            // Update the value of postSum[i]
            postSum[i] = maxSum;
        }
 
        // Stores the resultant maximum
        // sum of subarray
        long ans = 0;
 
        for (int i = 0; i < n; i++) {
 
            // Update the value of ans
            ans = Math.max(ans,
                           preSum[i]
                               + postSum[i + 1]);
        }
 
        // Print the resultant sum
        System.out.println(ans);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int arr[] = { 7, 6, -1, -4, -5, 7, 1 };
        maximumSum(arr, arr.length);
    }
}

Python3

# Python program for the above approach
 
# Function to find maximum
# subarray sum possible after
# removing at most one subarray
def maximumSum(arr, n) :
             
    preSum = [0] * n
  
    sum = 0
    maxSum = 0
 
    # Calculate the preSum[] array
    for i in range(n):
  
        # Update the value of sum
        sum = max(arr[i], sum + arr[i])
  
        # Update the value of maxSum
        maxSum = max(maxSum,
                          sum)
  
        # Update the value of preSum[i]
        preSum[i] = maxSum
         
 
    sum = 0
    maxSum = 0
  
    postSum = [0] * (n + 1)
  
    # Calculate the postSum[] array
    for i in range(n-1, -1, -1):
             
        # Update the value of sum
        sum = max(arr[i],
                       sum + arr[i])
  
        # Update the value of maxSum
        maxSum = max(maxSum,
                          sum)
  
        # Update the value of postSum[i]
        postSum[i] = maxSum
         
  
    # Stores the resultant maximum
    # sum of subarray
    ans = 0
  
    for i in range(n):
  
        # Update the value of ans
        ans = max(ans,
                       preSum[i]
                           + postSum[i + 1])
         
  
    # Print resultant sum
    print(ans)
     
# Driver code
arr = [ 7, 6, -1, -4, -5, 7, 1]
N = len(arr)
maximumSum(arr, N)
 
# This code is contributed by sanjoy_62.

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Function to find maximum
// subarray sum possible after
// removing at most one subarray
public static void maximumSum(int[] arr, int n)
{
    long[] preSum = new long[n];
    long sum = 0;
    long maxSum = 0;
 
    // Calculate the preSum[] array
    for(int i = 0; i < n; i++)
    {
         
        // Update the value of sum
        sum = Math.Max(arr[i], sum + arr[i]);
 
        // Update the value of maxSum
        maxSum = Math.Max(maxSum, sum);
 
        // Update the value of preSum[i]
        preSum[i] = maxSum;
    }
 
    sum = 0;
    maxSum = 0;
 
    long[] postSum = new long[n + 1];
 
    // Calculate the postSum[] array
    for(int i = n - 1; i >= 0; i--)
    {
         
        // Update the value of sum
        sum = Math.Max(arr[i], sum + arr[i]);
 
        // Update the value of maxSum
        maxSum = Math.Max(maxSum, sum);
 
        // Update the value of postSum[i]
        postSum[i] = maxSum;
    }
 
    // Stores the resultant maximum
    // sum of subarray
    long ans = 0;
 
    for(int i = 0; i < n; i++)
    {
         
        // Update the value of ans
        ans = Math.Max(ans, preSum[i] +
                            postSum[i + 1]);
    }
 
    // Print the resultant sum
    Console.WriteLine(ans);
}
 
// Driver code
static void Main()
{
    int[] arr = { 7, 6, -1, -4, -5, 7, 1 };
    maximumSum(arr, arr.Length);
}
}
 
// This code is contributed by abhinavjain194

Javascript

<script>
 
// Javascript implementation of the above approach
 
    // Function to find maximum
    // subarray sum possible after
    // removing at most one subarray
    function maximumSum(
        arr, n)
    {
        let preSum = Array.from({length: n}, (_, i) => 0);
  
        let sum = 0;
        let maxSum = 0;
  
        // Calculate the preSum[] array
        for (let i = 0; i < n; i++) {
  
            // Update the value of sum
            sum = Math.max(arr[i],
                           sum + arr[i]);
  
            // Update the value of maxSum
            maxSum = Math.max(maxSum,
                              sum);
  
            // Update the value of preSum[i]
            preSum[i] = maxSum;
        }
  
        sum = 0;
        maxSum = 0;
  
        let postSum = Array.from({length: n+1}, (_, i) => 0);
  
        // Calculate the postSum[] array
        for (let i = n - 1; i >= 0; i--) {
  
            // Update the value of sum
            sum = Math.max(arr[i],
                           sum + arr[i]);
  
            // Update the value of maxSum
            maxSum = Math.max(maxSum,
                              sum);
  
            // Update the value of postSum[i]
            postSum[i] = maxSum;
        }
  
        // Stores the resultant maximum
        // sum of subarray
        let ans = 0;
  
        for (let i = 0; i < n; i++) {
  
            // Update the value of ans
            ans = Math.max(ans,
                           preSum[i]
                               + postSum[i + 1]);
        }
  
        // Print the resultant sum
        document.write(ans);
    }
  
  // Driver Code
     
    let arr = [ 7, 6, -1, -4, -5, 7, 1 ];
    maximumSum(arr, arr.length);
 
</script>
Producción: 

21

 

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por harshitnsharma 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 *