Número máximo de 1 consecutivos después de cambiar todos los 0 en un subarreglo de longitud K

Dada una array binaria arr[] de longitud N y un entero K , la tarea es encontrar el número máximo de unos consecutivos después de invertir todos los ceros en una subarreglo de longitud K.

Ejemplos:

Entrada: arr[]= {0, 0, 1, 1, 1, 1, 0, 1, 1, 0}, K = 2
Salida: 7 
Explicación:
Al tomar el subarreglo [6, 7] y convertir cero en uno obtenemos 7 consecutivos.
 

Entrada: arr[]= {0, 0, 1, 1, 0, 0, 0, 0}, K = 3
Salida: 5 
Explicación:
Al tomar el subarreglo [4, 6] y convertir cero en uno, obtenemos 5 consecutivos unos. 
 

Enfoque: Para resolver el problema, siga los pasos que se detallan a continuación:

• Inicialice una variable, digamos trav , que va a iterar en la array desde cada posición i hasta (0 a i-1) en la dirección izquierda y desde (i+k hasta n-1) en la dirección derecha .
• Verifique y mantenga una cuenta de que ningún cero se interpone en su camino en ninguna dirección mientras itera en la array.
• Si hay un 0, salga del bucle en esa dirección.
• Entonces, en última instancia, para i a i + k , si hay algún cero, ya lo estamos cambiando a 1, por lo que no es necesario contar el número de unos en este rango, ya que será igual al número entero K solamente.

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 number of
// consecutive 1's after flipping all
// zero in a K length subarray
int findmax(int arr[], int n, int k)
{
    // Initialize variable
    int trav, i;
    int c = 0, maximum = 0;
 
    // Iterate until n-k+1 as we
    // have to go till i+k
    for (i = 0; i < n - k + 1; i++) {
        trav = i - 1;
        c = 0;
 
        /*Iterate in the array in left direction
        till you get 1 else break*/
        while (trav >= 0 && arr[trav] == 1) {
            trav--;
            c++;
        }
        trav = i + k;
 
        /*Iterate in the array in right direction
        till you get 1 else break*/
        while (trav < n && arr[trav] == 1) {
            trav++;
            c++;
        }
        c += k;
 
        // Compute the maximum length
        if (c > maximum)
            maximum = c;
    }
 
    // Return the length
    return maximum;
}
 
// Driver code
int main()
{
    int k = 3;
    // Array initialization
    int arr[] = { 0, 0, 1, 1, 0, 0, 0, 0 };
 
    // Size of array
    int n = sizeof arr / sizeof arr[0];
    int ans = findmax(arr, n, k);
    cout << ans << '\n';
}

// Java program for the above approach
import java.util.*;
 
class GFG{
     
// Function to find the maximum number of
// consecutive 1's after flipping all
// zero in a K length subarray
static int findmax(int arr[], int n, int k)
{
     
    // Initialize variable
    int trav, i;
    int c = 0, maximum = 0;
     
    // Iterate until n-k+1 as we
    // have to go till i+k
    for(i = 0; i < n - k + 1; i++)
    {
        trav = i - 1;
        c = 0;
     
        // Iterate in the array in left direction
        // till you get 1 else break
        while (trav >= 0 && arr[trav] == 1)
        {
            trav--;
            c++;
        }
        trav = i + k;
     
        // Iterate in the array in right direction
        // till you get 1 else break
        while (trav < n && arr[trav] == 1)
        {
            trav++;
            c++;
        }
        c += k;
     
        // Compute the maximum length
        if (c > maximum)
            maximum = c;
    }
     
    // Return the length
    return maximum;
}
 
// Driver code
public static void main(String args[])
{
    int k = 3;
     
    // Array initialization
    int arr[] = { 0, 0, 1, 1, 0, 0, 0, 0 };
 
    // Size of array
    int n = arr.length;
    int ans = findmax(arr, n, k);
     
    System.out.println(ans);
}
}
 
// This code is contributed by Stream_Cipher

# Python3 program for the above approach
 
# Function to find the maximum number of
# consecutive 1's after flipping all
# zero in a K length subarray
def findmax(arr, n, k):
     
    # Initialize variable
    trav, i = 0, 0
    c = 0
    maximum = 0
 
    # Iterate until n-k+1 as we
    # have to go till i+k
    while i < n - k + 1:
        trav = i - 1
        c = 0
 
        # Iterate in the array in left direction
        # till you get 1 else break
        while trav >= 0 and arr[trav] == 1:
            trav -= 1
            c += 1
        trav = i + k
 
        # Iterate in the array in right direction
        # till you get 1 else break
        while (trav < n and arr[trav] == 1):
            trav += 1
            c += 1
 
        c += k
 
        # Compute the maximum length
        if (c > maximum):
            maximum = c
        i += 1
 
    # Return the length
    return maximum
 
# Driver code
if __name__ == '__main__':
    k = 3
     
    # Array initialization
    arr = [0, 0, 1, 1, 0, 0, 0, 0]
 
    # Size of array
    n = len(arr)
    ans = findmax(arr, n, k)
    print(ans)
 
# This code is contributed by Mohit Kumar

// C# program for the above approach
using System;
 
class GFG{
     
// Function to find the maximum number of
// consecutive 1's after flipping all
// zero in a K length subarray
static int findmax(int []arr, int n, int k)
{
     
    // Initialize variable
    int trav, i;
    int c = 0, maximum = 0;
     
    // Iterate until n-k+1 as we
    // have to go till i+k
    for(i = 0; i < n - k + 1; i++)
    {
        trav = i - 1;
        c = 0;
     
        // Iterate in the array in left direction
        // till you get 1 else break
        while (trav >= 0 && arr[trav] == 1)
        {
            trav--;
            c++;
        }
        trav = i + k;
     
        // Iterate in the array in right direction
        // till you get 1 else break
        while (trav < n && arr[trav] == 1)
        {
            trav++;
            c++;
        }
        c += k;
     
        // Compute the maximum length
        if (c > maximum)
            maximum = c;
    }
     
    // Return the length
    return maximum;
}
 
// Driver code
public static void Main()
{
    int k = 3;
     
    // Array initialization
    int []arr = { 0, 0, 1, 1, 0, 0, 0, 0 };
 
    // Size of array
    int n = arr.Length;
    int ans = findmax(arr, n, k);
     
    Console.WriteLine(ans);
}
}
 
// This code is contributed by Stream_Cipher

<script>
// Javascript program for the above approach
 
// Function to find the maximum number of
// consecutive 1's after flipping all
// zero in a K length subarray
function findmax(arr, n, k) {
    // Initialize variable
    let trav, i;
    let c = 0, maximum = 0;
 
    // Iterate until n-k+1 as we
    // have to go till i+k
    for (i = 0; i < n - k + 1; i++) {
        trav = i - 1;
        c = 0;
 
        /*Iterate in the array in left direction
        till you get 1 else break*/
        while (trav >= 0 && arr[trav] == 1) {
            trav--;
            c++;
        }
        trav = i + k;
 
        /*Iterate in the array in right direction
        till you get 1 else break*/
        while (trav < n && arr[trav] == 1) {
            trav++;
            c++;
        }
        c += k;
 
        // Compute the maximum length
        if (c > maximum)
            maximum = c;
    }
 
    // Return the length
    return maximum;
}
 
// Driver code
 
let k = 3;
// Array initialization
let arr = [0, 0, 1, 1, 0, 0, 0, 0];
 
// Size of array
let n = arr.length;
let ans = findmax(arr, n, k);
document.write(ans)
 
// This code is contributed by _saurabh_jaiswal.
</script>

5

Complejidad temporal: O(N ² )

Espacio Auxiliar: O(1)