El subarreglo más largo que tiene un conteo de 1s uno más que un conteo de 0s

Dada una array de tamaño n que contiene solo 0 y 1. El problema es encontrar la longitud del subarreglo más largo que tenga una cuenta de 1 más que una cuenta de 0. 
Ejemplos: 
 

Input : arr = {0, 1, 1, 0, 0, 1}
Output : 5
From index 1 to 5.

Input : arr[] = {1, 0, 0, 1, 0}
Output : 1

Enfoque: Los siguientes son los pasos:
 

1. Considere todos los 0 en la array como ‘-1’.
2. Inicialice sum = 0 y maxLen = 0.
3. Cree una tabla hash que tenga tuplas (suma, índice) .
4. Para i = 0 a n-1, realice los siguientes pasos:
   1. Si arr[i] es ‘0’, acumula ‘-1’ para sumar ; de lo contrario, acumula ‘1’ para sumar .
   2. Si sum == 1, actualice maxLen = i+1.
   3. De lo contrario, compruebe si la suma está presente en la tabla hash o no. Si no está presente, agréguelo a la tabla hash como (suma, i) par.
   4. Compruebe si (sum-1) está presente en la tabla hash o no. si está presente, obtenga el índice de (suma-1) de la tabla hash como índice . Ahora verifique si maxLen es menor que (i-index), luego actualice maxLen = (i-index).
5. Devuelve maxLen.

// C++ implementation to find the length of
// longest subarray having count of 1's one
// more than count of 0's
#include <bits/stdc++.h>
using namespace std;
 
// function to find the length of longest
// subarray having count of 1's one more
// than count of 0's
int lenOfLongSubarr(int arr[], int n)
{
    // unordered_map 'um' implemented as
    // hash table
    unordered_map<int, int> um;
    int sum = 0, maxLen = 0;
 
    // traverse the given array
    for (int i = 0; i < n; i++) {
 
        // consider '0' as '-1'
        sum += arr[i] == 0 ? -1 : 1;
 
        // when subarray starts form index '0'
        if (sum == 1)
            maxLen = i + 1;
 
        // make an entry for 'sum' if it is
        // not present in 'um'
        else if (um.find(sum) == um.end())
            um[sum] = i;
 
        // check if 'sum-1' is present in 'um'
        // or not
        if (um.find(sum - 1) != um.end()) {
 
            // update maxLength
            if (maxLen < (i - um[sum - 1]))
                maxLen = i - um[sum - 1];
        }
    }
 
    // required maximum length
    return maxLen;
}
 
// Driver program to test above
int main()
{
    int arr[] = { 0, 1, 1, 0, 0, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Length = "
         << lenOfLongSubarr(arr, n);
    return 0;
}

// Java implementation to find the length of
// longest subarray having count of 1's one
// more than count of 0's
import java.util.*;
 
class GFG
{
 
// function to find the length of longest
// subarray having count of 1's one more
// than count of 0's
static int lenOfLongSubarr(int arr[], int n)
{
    // unordered_map 'um' implemented as
    // hash table
    HashMap<Integer,
            Integer> um = new HashMap<Integer,
                                      Integer>();
    int sum = 0, maxLen = 0;
 
    // traverse the given array
    for (int i = 0; i < n; i++)
    {
 
        // consider '0' as '-1'
        sum += arr[i] == 0 ? -1 : 1;
 
        // when subarray starts form index '0'
        if (sum == 1)
            maxLen = i + 1;
 
        // make an entry for 'sum' if it is
        // not present in 'um'
        else if (!um.containsKey(sum))
            um. put(sum, i);
 
        // check if 'sum-1' is present in 'um'
        // or not
        if (um.containsKey(sum - 1))
        {
 
            // update maxLength
            if (maxLen < (i - um.get(sum - 1)))
                maxLen = i - um.get(sum - 1);
        }
    }
 
    // required maximum length
    return maxLen;
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 0, 1, 1, 0, 0, 1 };
    int n = arr.length;
    System.out.println("Length = " +
               lenOfLongSubarr(arr, n));
}
}
 
// This code is contributed by Princi Singh

# Python 3 implementation to find the length of
# longest subarray having count of 1's one
# more than count of 0's
 
# function to find the length of longest
# subarray having count of 1's one more
# than count of 0's
def lenOfLongSubarr(arr, n):
     
    # unordered_map 'um' implemented as
    # hash table
    um = {i:0 for i in range(10)}
    sum = 0
    maxLen = 0
 
    # traverse the given array
    for i in range(n):
         
        # consider '0' as '-1'
        if arr[i] == 0:
            sum += -1
        else:
            sum += 1
 
        # when subarray starts form index '0'
        if (sum == 1):
            maxLen = i + 1
 
        # make an entry for 'sum' if it is
        # not present in 'um'
        elif (sum not in um):
            um[sum] = i
 
        # check if 'sum-1' is present in 'um'
        # or not
        if ((sum - 1) in um):
            # update maxLength
            if (maxLen < (i - um[sum - 1])):
                maxLen = i - um[sum - 1]
 
    # required maximum length
    return maxLen
 
# Driver code
if __name__ == '__main__':
    arr = [0, 1, 1, 0, 0, 1]
    n = len(arr)
    print("Length =",lenOfLongSubarr(arr, n))
     
# This code is contributed by
# Surendra_Gangwar

// C# implementation to find the length of
// longest subarray having count of 1's one
// more than count of 0's
using System;
using System.Collections.Generic;
     
class GFG
{
 
// function to find the length of longest
// subarray having count of 1's one more
// than count of 0's
static int lenOfLongSubarr(int []arr, int n)
{
    // unordered_map 'um' implemented as
    // hash table
    Dictionary<int,
               int> um = new Dictionary<int,
                                        int>();
    int sum = 0, maxLen = 0;
 
    // traverse the given array
    for (int i = 0; i < n; i++)
    {
 
        // consider '0' as '-1'
        sum += arr[i] == 0 ? -1 : 1;
 
        // when subarray starts form index '0'
        if (sum == 1)
            maxLen = i + 1;
 
        // make an entry for 'sum' if it is
        // not present in 'um'
        else if (!um.ContainsKey(sum))
            um.Add(sum, i);
 
        // check if 'sum-1' is present in 'um'
        // or not
        if (um.ContainsKey(sum - 1))
        {
 
            // update maxLength
            if (maxLen < (i - um[sum - 1]))
                maxLen = i - um[sum - 1];
        }
    }
 
    // required maximum length
    return maxLen;
}
 
// Driver Code
public static void Main(String[] args)
{
    int []arr = { 0, 1, 1, 0, 0, 1 };
    int n = arr.Length;
    Console.WriteLine("Length = " +
            lenOfLongSubarr(arr, n));
}
}
 
// This code is contributed by Rajput-Ji

<script>
 
 
// Javascript implementation to find the length of
// longest subarray having count of 1's one
// more than count of 0's
 
// function to find the length of longest
// subarray having count of 1's one more
// than count of 0's
function lenOfLongSubarr(arr, n)
{
    // unordered_map 'um' implemented as
    // hash table
    var um = new Map();
    var sum = 0, maxLen = 0;
 
    // traverse the given array
    for (var i = 0; i < n; i++) {
 
        // consider '0' as '-1'
        sum += arr[i] == 0 ? -1 : 1;
 
        // when subarray starts form index '0'
        if (sum == 1)
            maxLen = i + 1;
 
        // make an entry for 'sum' if it is
        // not present in 'um'
        else if (!um.has(sum))
            um.set(sum, i);
 
        // check if 'sum-1' is present in 'um'
        // or not
        if (um.has(sum - 1)) {
 
            // update maxLength
            if (maxLen < (i - um.get(sum - 1)))
                maxLen = i - um.get(sum - 1);
        }
    }
 
    // required maximum length
    return maxLen;
}
 
// Driver program to test above
var arr = [0, 1, 1, 0, 0, 1];
var n = arr.length;
document.write( "Length = "
      + lenOfLongSubarr(arr, n));
 
// This code is contributed by itsok.
</script>

Producción: 
 

Length = 5

Complejidad de tiempo: O(n) 
Espacio auxiliar: O(n)
Este artículo es una contribución de Ayush Jauhari . 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 contribuido@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.