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++
// 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
// 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
# 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#
// 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.
Javascript
<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>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por kartikey134 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA