Suma máxima de subarreglo con el mismo primer y último elemento formado al eliminar elementos

Dada una array arr[] de N enteros, la tarea es encontrar la suma máxima de subarreglo que tenga una longitud de al menos 2 cuyo primer y último elemento sean iguales después de eliminar cualquier cantidad de elementos del arreglo. Si no existe tal array, imprima 0 .

Ejemplos:

Entrada: arr[] = {-1, -3, -2, 4, -1, 3}
Salida: 2
Explicación: elija la subarray { -1, -3, -2, 4, -1} y elimínela los elementos -3 y -2 lo que hace que el subarreglo sea {-1, 4, -1} con suma igual a 2 que es el máximo.

Entrada: arr[] = {-1}
Salida: 0

Enfoque: el problema dado se puede resolver utilizando la idea de que primero encuentre todos los subarreglos que tengan el primer y el último elemento iguales y elimine todos los elementos negativos entre el primero y el último elemento. Esta idea puede ser implementada por la idea discutida en este artículo utilizando un mapa desordenado . Siga los pasos a continuación para resolver el problema dado:

• Inicialice una variable, digamos res como INT_MIN que almacena la suma máxima resultante del subarreglo.
• Inicialice una variable, digamos currentSum como 0 que almacena la suma del prefijo en ejecución de la array .
• Inicialice un mapa_desordenado , digamos memo[] que almacena el valor de cada elemento de la array asignado con su suma de prefijo.
• Itere sobre el rango [0, N) usando la variable i y realice las siguientes tareas:
  • Agregue el valor del elemento de array actual arr[i] a la variable currentSum .
  • Si arr[i] está presente en el mapa , y si el valor de arr[i] es positivo, actualice el valor de res al máximo de res y (currentSum – M[arr[i]] + arr[i]) . De lo contrario, actualice el valor de res al máximo de res y (currentSum – M[arr[i]] + 2*arr[i]) .
  • De lo contrario, inserte el valor arr[i] asignado con currentSum .
  • Si el valor actual arr[i] es negativo, entonces disminúyalo desde currentSum para excluir el elemento negativo del posible subarreglo.
• Después de completar los pasos anteriores, imprima el valor de res como resultado.

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
// of sub-array
int maximumSubarraySum(vector<int>& arr)
{
 
    // Initialize the variables
    int N = arr.size();
    unordered_map<int, int> memo;
    int res = INT_MIN;
    int currsum = 0, currval = 0;
 
    // Traverse over the range
    for (int i = 0; i < N; ++i) {
 
        // Add the current value to the
        // variable currsum for prefix sum
        currval = arr[i];
        currsum = currsum + currval;
 
        // Calculate the result
        if (memo.count(currval) != 0) {
            if (currval > 0)
                res = max(
                    res,
                    currsum - memo[currval]
                        + currval);
            else
                res = max(
                    res,
                    currsum - memo[currval]
                        + 2 * currval);
        }
        else
            memo[currval] = currsum;
        if (currval < 0)
            currsum = currsum - currval;
    }
 
    // Return the answer
    return res;
}
 
// Driver Code
int main()
{
    vector<int> arr = { -1, -3, 4, 0, -1, -2 };
    cout << maximumSubarraySum(arr);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG
{
   
    // Function to find the maximum sum
    // of sub-array
    static int maximumSubarraySum(int arr[], int N)
    {
 
        // Initialize the variables
        HashMap<Integer, Integer> memo = new HashMap<>();
        int res = Integer.MIN_VALUE;
        int currsum = 0, currval = 0;
 
        // Traverse over the range
        for (int i = 0; i < N; ++i) {
 
            // Add the current value to the
            // variable currsum for prefix sum
            currval = arr[i];
            currsum = currsum + currval;
 
            // Calculate the result
            if (memo.containsKey(currval)) {
                if (currval > 0)
                    res = Math.max(
                        res, currsum - memo.get(currval)
                                 + currval);
                else
                    res = Math.max(
                        res, currsum - memo.get(currval)
                                 + 2 * currval);
            }
            else
                memo.put(currval, currsum);
            if (currval < 0)
                currsum = currsum - currval;
        }
 
        // Return the answer
        return res;
    }
   
    // Driver Code
    public static void main(String[] args)
    {
        int arr[] = { -1, -3, 4, 0, -1, -2 };
        int N = 6;
        System.out.println(maximumSubarraySum(arr, N));
    }
}
 
// This code is contributed by dwivediyash

# Python3 program for the above approach
import sys
 
# Function to find the maximum sum
# of sub-array
def maximumSubarraySum(arr) :
 
    # Initialize the variables
    N = len(arr);
    memo = {};
    res = -(sys.maxsize - 1);
    currsum = 0;
    currval = 0;
 
    # Traverse over the range
    for i in range(N) :
 
        # Add the current value to the
        # variable currsum for prefix sum
        currval = arr[i];
        currsum = currsum + currval;
 
        # Calculate the result
        if currval in memo :
             
            if (currval > 0) :
                res = max(res,currsum - memo[currval] + currval);
            else :
                res = max(res,currsum - memo[currval] + 2 * currval);
         
        else :
            memo[currval] = currsum;
             
        if (currval < 0) :
            currsum = currsum - currval;
 
    # Return the answer
    return res;
 
 
# Driver Code
if __name__ == "__main__" :
 
    arr = [ -1, -3, 4, 0, -1, -2 ];
    print(maximumSubarraySum(arr));
 
    # This code is contributed by AnkThon

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
    // Function to find the maximum sum
    // of sub-array
    static int maximumSubarraySum(int[] arr, int N)
    {
 
        // Initialize the variables
        Dictionary<int, int> memo = new
                Dictionary<int, int>();
        int res = Int32.MinValue;
        int currsum = 0, currval = 0;
 
        // Traverse over the range
        for (int i = 0; i < N; ++i) {
 
            // Add the current value to the
            // variable currsum for prefix sum
            currval = arr[i];
            currsum = currsum + currval;
 
            // Calculate the result
            if (memo.ContainsKey(currval)) {
                if (currval > 0)
                    res = Math.Max(
                        res, currsum - memo[(currval)]
                                 + currval);
                else
                    res = Math.Max(
                        res, currsum - memo[(currval)]
                                 + 2 * currval);
            }
            else
                memo.Add(currval, currsum);
            if (currval < 0)
                currsum = currsum - currval;
        }
 
        // Return the answer
        return res;
    }
 
// Driver Code
public static void Main()
{
    int[] arr = { -1, -3, 4, 0, -1, -2 };
    int N = 6;
    Console.WriteLine(maximumSubarraySum(arr, N));
}
}
 
// This code is contributed by sanjoy_62.

<script>
        // JavaScript Program to implement
        // the above approach
 
        // Function to find the maximum sum
        // of sub-array
        function maximumSubarraySum(arr) {
 
            // Initialize the variables
            let N = arr.length;
            let memo = new Map();
            let res = -99999999;
            let currsum = 0, currval = 0;
 
            // Traverse over the range
            for (let i = 0; i < N; ++i) {
 
                // Add the current value to the
                // variable currsum for prefix sum
                currval = arr[i];
                currsum = currsum + currval;
 
                // Calculate the result
                if (memo.has(currval)) {
                    if (currval > 0)
                        res = Math.max(
                            res,
                            currsum - memo.get(currval)
                            + currval);
                    else
                        res = Math.max(
                            res,
                            currsum - memo.get(currval)
                            + 2 * currval);
                }
                else
                    memo.set(currval, currsum);
                if (currval < 0)
                    currsum = currsum - currval;
            }
 
            // Return the answer
            return res;
        }
 
        // Driver Code
        let arr = [-1, -3, 4, 0, -1, -2];
        document.write(maximumSubarraySum(arr));
 
// This code is contributed by Potta Lokesh
    </script>

2

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