Dada una array arr[] de longitud N , encuentre la longitud de la sub-array más larga con una suma igual a 0.
Ejemplos:
Entrada: arr[] = {15, -2, 2, -8, 1, 7, 10, 23}
Salida: 5
Explicación: El subarreglo más largo con elementos que suman 0 es {-2, 2, – 8, 1, 7}Entrada: arr[] = {1, 2, 3}
Salida: 0
Explicación: No hay subarreglo con suma 0Entrada: arr[] = {1, 0, 3}
Salida: 1
Explicación: El subarreglo más largo con elementos que suman 0 es {0}
Enfoque ingenuo : siga los pasos a continuación para resolver el problema utilizando este enfoque:
- Considere todos los subconjuntos uno por uno y verifique la suma de cada subconjunto.
- Si la suma del subarreglo actual es igual a cero, actualice la longitud máxima en consecuencia
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;
// Returns length of the largest
// subarray with 0 sum
int maxLen(int arr[], int N)
{
// Initialize result
int max_len = 0;
// Pick a starting point
for (int i = 0; i < N; i++) {
// Initialize currr_sum for
// every starting point
int curr_sum = 0;
// Try all subarrays starting with 'i'
for (int j = i; j < N; j++) {
curr_sum += arr[j];
// If curr_sum becomes 0,
// then update max_len
// if required
if (curr_sum == 0)
max_len = max(max_len, j - i + 1);
}
}
return max_len;
}
// Driver's Code
int main()
{
int arr[] = {15, -2, 2, -8, 1, 7, 10, 23};
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
cout << "Length of the longest 0 sum subarray is "
<< maxLen(arr, N);
return 0;
}
Java
// Java code for the above approach
class GFG {
// Returns length of the largest subarray
// with 0 sum
static int maxLen(int arr[], int N)
{
int max_len = 0;
// Pick a starting point
for (int i = 0; i < N; i++) {
// Initialize curr_sum for every
// starting point
int curr_sum = 0;
// try all subarrays starting with 'i'
for (int j = i; j < N; j++) {
curr_sum += arr[j];
// If curr_sum becomes 0, then update
// max_len
if (curr_sum == 0)
max_len = Math.max(max_len, j - i + 1);
}
}
return max_len;
}
// Driver's code
public static void main(String args[])
{
int arr[] = {15, -2, 2, -8, 1, 7, 10, 23};
int N = arr.length;
// Function call
System.out.println("Length of the longest 0 sum "
+ "subarray is " + maxLen(arr, N));
}
}
Python3
# Python program for the above approach
# returns the length
def maxLen(arr):
# initialize result
max_len = 0
# pick a starting point
for i in range(len(arr)):
# initialize sum for every starting point
curr_sum = 0
# try all subarrays starting with 'i'
for j in range(i, len(arr)):
curr_sum += arr[j]
# if curr_sum becomes 0, then update max_len
if curr_sum == 0:
max_len = max(max_len, j-i + 1)
return max_len
# Driver's code
if __name__ == "__main__":
# test array
arr = [15, -2, 2, -8, 1, 7, 10, 13]
# Function call
print ("Length of the longest 0 sum subarray is % d" % maxLen(arr))
C#
// C# code for the above approach
using System;
class GFG {
// Returns length of the
// largest subarray with 0 sum
static int maxLen(int[] arr, int N)
{
int max_len = 0;
// Pick a starting point
for (int i = 0; i < N; i++) {
// Initialize curr_sum
// for every starting point
int curr_sum = 0;
// try all subarrays
// starting with 'i'
for (int j = i; j < N; j++) {
curr_sum += arr[j];
// If curr_sum becomes 0,
// then update max_len
if (curr_sum == 0)
max_len = Math.Max(max_len,
j - i + 1);
}
}
return max_len;
}
// Driver's code
static public void Main()
{
int[] arr = {15, -2, 2, -8,
1, 7, 10, 23};
int N = arr.Length;
// Function call
Console.WriteLine("Length of the longest 0 sum "
+ "subarray is " + maxLen(arr, N));
}
}
PHP
<?php
// PHP program for the above approach
// Returns length of the
// largest subarray with 0 sum
function maxLen($arr, $N)
{
// Initialize result
$max_len = 0;
// Pick a starting point
for ($i = 0; $i < $N; $i++)
{
// Initialize currr_sum
// for every starting point
$curr_sum = 0;
// try all subarrays
// starting with 'i'
for ($j = $i; $j < $N; $j++)
{
$curr_sum += $arr[$j];
// If curr_sum becomes 0,
// then update max_len
// if required
if ($curr_sum == 0)
$max_len = max($max_len,
$j - $i + 1);
}
}
return $max_len;
}
// Driver Code
$arr = array(15, -2, 2, -8,
1, 7, 10, 23);
$N = sizeof($arr);
// Function call
echo "Length of the longest 0 " .
"sum subarray is ",
maxLen($arr, $N);
?>
Javascript
<script>
// Javascript code to find the largest
// subarray with 0 sum
// Returns length of the
// largest subarray with 0 sum
function maxLen(arr, N)
{
let max_len = 0;
// Pick a starting point
for (let i = 0; i < N; i++) {
// Initialize curr_sum
// for every starting point
let curr_sum = 0;
// try all subarrays
// starting with 'i'
for (let j = i; j < N; j++) {
curr_sum += arr[j];
// If curr_sum becomes 0,
// then update max_len
if (curr_sum == 0)
max_len = Math.max(max_len, j - i + 1);
}
}
return max_len;
}
// Driver's code
let arr = [15, -2, 2, -8, 1, 7, 10, 23];
let N = arr.length;
// Function call
document.write("Length of the longest 0 sum " + "subarray is " + maxLen(arr, N));
</script>
Producción
Length of the longest 0 sum subarray is 5
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente 1 (mapa hash) : siga la siguiente idea para resolver el problema utilizando este enfoque:
Cree una suma variable y mientras atraviesa la array de entrada, para cada índice agregue el valor del elemento en la variable de suma y luego almacene el par suma-índice en un mapa hash . Entonces, si el mismo valor aparece dos veces en la array, se garantizará que la array particular será una sub-array de suma cero.
Prueba matemática:
prefijo(i) = arr[0] + arr[1] +…+ arr[i]
prefijo(j) = arr[0] + arr[1] +…+ arr[j], j > i
ifprefix(i) == prefijo(j) luego prefijo(j) – prefijo(i) = 0 eso significa arr[i+1] + .. + arr[j] = 0 , por lo que un subarreglo tiene suma cero, y la longitud de ese subarreglo es j-i+1
Siga los pasos que se mencionan a continuación para implementar el enfoque:
- Cree una variable (sum) , length (max_len) y un mapa hash (hm) para almacenar el par suma-índice como un par clave-valor.
- Recorra la array de entrada y, para cada índice, actualice el valor de sum = sum + array[i].
- Verifique cada índice, si la suma actual está presente en el mapa hash o no.
- Si está presente, actualice el valor de max_len a una diferencia máxima de dos índices (índice actual e índice en el mapa hash) y max_len.
- De lo contrario, coloque el valor (suma) en el mapa hash, con el índice como un par clave-valor.
- Imprime la longitud máxima (max_len).
A continuación se muestra una ejecución en seco del enfoque anterior:
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;
// Returns Length of the required subarray
int maxLen(int arr[], int N)
{
// Map to store the previous sums
unordered_map<int, int> presum;
int sum = 0; // Initialize the sum of elements
int max_len = 0; // Initialize result
// Traverse through the given array
for (int i = 0; i < N; i++) {
// Add current element to sum
sum += arr[i];
if (arr[i] == 0 && max_len == 0)
max_len = 1;
if (sum == 0)
max_len = i + 1;
// Look for this sum in Hash table
if (presum.find(sum) != presum.end()) {
// If this sum is seen before, then update
// max_len
max_len = max(max_len, i - presum[sum]);
}
else {
// Else insert this sum with index
// in hash table
presum[sum] = i;
}
}
return max_len;
}
// Driver's Code
int main()
{
int arr[] = { 15, -2, 2, -8, 1, 7, 10, 23 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
cout << "Length of the longest 0 sum subarray is "
<< maxLen(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.HashMap;
class MaxLenZeroSumSub {
// Returns length of the maximum length
// subarray with 0 sum
static int maxLen(int arr[])
{
// Creates an empty hashMap hM
HashMap<Integer, Integer> hM
= new HashMap<Integer, Integer>();
int sum = 0; // Initialize sum of elements
int max_len = 0; // Initialize result
// Traverse through the given array
for (int i = 0; i < arr.length; i++) {
// Add current element to sum
sum += arr[i];
if (arr[i] == 0 && max_len == 0)
max_len = 1;
if (sum == 0)
max_len = i + 1;
// Look this sum in hash table
Integer prev_i = hM.get(sum);
// If this sum is seen before, then update
// max_len if required
if (prev_i != null)
max_len = Math.max(max_len, i - prev_i);
else // Else put this sum in hash table
hM.put(sum, i);
}
return max_len;
}
// Drive's code
public static void main(String arg[])
{
int arr[] = {15, -2, 2, -8, 1, 7, 10, 23};
// Function call
System.out.println(
"Length of the longest 0 sum subarray is "
+ maxLen(arr));
}
}
Python3
# Python program for the above approach
# Returns the maximum length
def maxLen(arr):
# NOTE: Dictionary in python is
# implemented as Hash Maps
# Create an empty hash map (dictionary)
hash_map = {}
# Initialize result
max_len = 0
# Initialize sum of elements
curr_sum = 0
# Traverse through the given array
for i in range(len(arr)):
# Add the current element to the sum
curr_sum += arr[i]
if arr[i] == 0 and max_len == 0:
max_len = 1
if curr_sum == 0:
max_len = i + 1
# NOTE: 'in' operation in dictionary
# to search key takes O(1). Look if
# current sum is seen before
if curr_sum in hash_map:
max_len = max(max_len, i - hash_map[curr_sum])
else:
# else put this sum in dictionary
hash_map[curr_sum] = i
return max_len
# Driver's code
if __name__ == "__main__":
# test array
arr = [15, -2, 2, -8, 1, 7, 10, 13]
# Function call
print("Length of the longest 0 sum subarray is % d" % maxLen(arr))
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class MaxLenZeroSumSub {
// Returns length of the maximum
// length subarray with 0 sum
static int maxLen(int[] arr)
{
// Creates an empty hashMap hM
Dictionary<int, int> hM
= new Dictionary<int, int>();
int sum = 0; // Initialize sum of elements
int max_len = 0; // Initialize result
// Traverse through the given array
for (int i = 0; i < arr.GetLength(0); i++) {
// Add current element to sum
sum += arr[i];
if (arr[i] == 0 && max_len == 0)
max_len = 1;
if (sum == 0)
max_len = i + 1;
// Look this sum in hash table
int prev_i = 0;
if (hM.ContainsKey(sum)) {
prev_i = hM[sum];
}
// If this sum is seen before, then update
// max_len if required
if (hM.ContainsKey(sum))
max_len = Math.Max(max_len, i - prev_i);
else {
// Else put this sum in hash table
if (hM.ContainsKey(sum))
hM.Remove(sum);
hM.Add(sum, i);
}
}
return max_len;
}
// Driver's code
public static void Main()
{
int[] arr = { 15, -2, 2, -8, 1, 7, 10, 23 };
// Function call
Console.WriteLine(
"Length of the longest 0 sum subarray is "
+ maxLen(arr));
}
}
Javascript
<script>
// Javascript program to find maximum length subarray with 0 sum
// Returns length of the maximum length subarray with 0 sum
function maxLen(arr)
{
// Creates an empty hashMap hM
let hM = new Map();
let sum = 0; // Initialize sum of elements
let max_len = 0; // Initialize result
// Traverse through the given array
for (let i = 0; i < arr.length; i++) {
// Add current element to sum
sum += arr[i];
if (arr[i] == 0 && max_len == 0)
max_len = 1;
if (sum == 0)
max_len = i + 1;
// Look this sum in hash table
let prev_i = hM.get(sum);
// If this sum is seen before, then update max_len
// if required
if (prev_i != null)
max_len = Math.max(max_len, i - prev_i);
else // Else put this sum in hash table
hM.set(sum, i);
}
return max_len;
}
// Driver's program
let arr = [15, -2, 2, -8, 1, 7, 10, 23];
// Function call
document.write("Length of the longest 0 sum subarray is "
+ maxLen(arr));
</script>
Producción
Length of the longest 0 sum subarray is 5
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
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