Longitud de la segunda secuencia más larga de 1 consecutivos en una array binaria

Dada una array binaria arr[] de tamaño N , la tarea es encontrar la longitud de la segunda secuencia más larga de 1 consecutivos presentes en la array.

Ejemplos:

Entrada: arr[] = {1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0} 
Salida: 4 3 
Explicación: 
La secuencia más larga de consecutivos es 4, es decir, { array[7], … array[10]}. 
La segunda secuencia más larga de secuencias consecutivas es 3, es decir, {arr[0], … arr[2]}.

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

Enfoque: La idea es atravesar la array binaria dada y realizar un seguimiento de la longitud más grande y la segunda más grande de los consecutivos encontrados hasta el momento. A continuación se muestran los pasos: 

1. Inicialice las variables maxi , count y second_max para almacenar la longitud de la secuencia más larga, actual y segunda más larga de 1s consecutivos, respectivamente.
2. Iterar sobre la array dada dos veces.
3. Primero, recorra la array de izquierda a derecha. Por cada 1 encontrado, luego incremente el conteo y compárelo con el máximo hasta el momento. Si se encuentra 0, restablezca el conteo como 0.
4. En el segundo recorrido, encuentre el segundo conteo más largo requerido de 1 consecutivos siguiendo el procedimiento anterior.

A continuación se muestra la implementación del enfoque anterior: 

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find maximum
// and second maximum length
void FindMax(int arr[], int N)
{
    // Initialise maximum length
    int maxi = -1;
 
    // Initialise second maximum length
    int maxi2 = -1;
 
    // Initialise count
    int count = 0;
 
    // Iterate over the array
    for (int i = 0; i < N; ++i) {
 
        // If sequence ends
        if (arr[i] == 0)
 
            // Reset count
            count = 0;
 
        // Otherwise
        else {
 
            // Increase length
            // of current sequence
            count++;
 
            // Update maximum
            maxi = max(maxi, count);
        }
    }
 
    // Traverse the given array
    for (int i = 0; i < N; i++) {
 
        // If sequence continues
        if (arr[i] == 1) {
 
            // Increase length
            // of current sequence
            count++;
 
            // Update second max
            if (count > maxi2 && count < maxi) {
                maxi2 = count;
            }
        }
 
        // Reset count when 0 is found
        if (arr[i] == 0)
            count = 0;
    }
 
    maxi = max(maxi, 0);
    maxi2 = max(maxi2, 0);
 
    // Print the result
    cout << maxi2;
}
 
// Driver Code
int main()
{
    // Given array
    int arr[] = { 1, 1, 1, 0, 0, 1, 1 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    FindMax(arr, N);
    return 0;
}

// Java implementation of the above approach
import java.io.*;
import java.util.*;
 
class GFG{
     
// Function to find maximum
// and second maximum length
static void FindMax(int arr[], int N)
{
     
    // Initialise maximum length
    int maxi = -1;
 
    // Initialise second maximum length
    int maxi2 = -1;
 
    // Initialise count
    int count = 0;
 
    // Iterate over the array
    for(int i = 0; i < N; ++i)
    {
         
        // If sequence ends
        if (arr[i] == 0)
 
            // Reset count
            count = 0;
 
        // Otherwise
        else
        {
             
            // Increase length
            // of current sequence
            count++;
 
            // Update maximum
            maxi = Math.max(maxi, count);
        }
    }
 
    // Traverse the given array
    for(int i = 0; i < N; i++)
    {
         
        // If sequence continues
        if (arr[i] == 1)
        {
             
            // Increase length
            // of current sequence
            count++;
 
            // Update second max
            if (count > maxi2 &&
                count < maxi)
            {
                maxi2 = count;
            }
        }
         
        // Reset count when 0 is found
        if (arr[i] == 0)
            count = 0;
    }
 
    maxi = Math.max(maxi, 0);
    maxi2 = Math.max(maxi2, 0);
 
    // Print the result
    System.out.println( maxi2);
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 1, 1, 1, 0, 0, 1, 1 };
    int n = arr.length;
     
    FindMax(arr, n);
}
}
 
// This code is contributed by Stream_Cipher

# Python3 implementation of the above approach
 
# Function to find maximum
# and second maximum length
def FindMax(arr, N):
   
    # Initialise maximum length
    maxi = -1
 
    # Initialise second maximum length
    maxi2 = -1
 
    # Initialise count
    count = 0
 
    # Iterate over the array
    for i in range(N):
 
        # If sequence ends
        if (arr[i] == 0):
 
            # Reset count
            count = 0
 
        # Otherwise
        else:
 
            # Increase length
            # of current sequence
            count += 1
 
            # Update maximum
            maxi = max(maxi, count)
 
    # Traverse the given array
    for i in range(N):
 
        # If sequence continues
        if (arr[i] == 1):
 
            # Increase length
            # of current sequence
            count += 1
 
            # Update second max
            if (count > maxi2 and
                count < maxi):
                maxi2 = count
 
        # Reset count when 0 is found
        if (arr[i] == 0):
            count = 0
 
    maxi = max(maxi, 0)
    maxi2 = max(maxi2, 0)
 
    # Print the result
    print(maxi2)
 
# Driver Code
if __name__ == '__main__':
   
    # Given array
    arr = [1, 1, 1, 0, 0, 1, 1]
    N = len(arr)
 
    # Function Call
    FindMax(arr, N)
 
# This code is contributed by Mohit Kumar29

// C# implementation of the above approach
using System.Collections.Generic;
using System;
 
class GFG{
     
// Function to find maximum
// and second maximum length
static void FindMax(int []arr, int N)
{
     
    // Initialise maximum length
    int maxi = -1;
 
    // Initialise second maximum length
    int maxi2 = -1;
 
    // Initialise count
    int count = 0;
 
    // Iterate over the array
    for(int i = 0; i < N; ++i)
    {
         
        // If sequence ends
        if (arr[i] == 0)
 
            // Reset count
            count = 0;
 
        // Otherwise
        else
        {
             
            // Increase length
            // of current sequence
            count++;
 
            // Update maximum
            maxi = Math.Max(maxi, count);
        }
    }
     
    // Traverse the given array
    for(int i = 0; i < N; i++)
    {
 
        // If sequence continues
        if (arr[i] == 1)
        {
             
            // Increase length
            // of current sequence
            count++;
 
            // Update second max
            if (count > maxi2 &&
                count < maxi)
            {
                maxi2 = count;
            }
        }
         
        // Reset count when 0 is found
        if (arr[i] == 0)
            count = 0;
    }
     
    maxi = Math.Max(maxi, 0);
    maxi2 = Math.Max(maxi2, 0);
 
    // Print the result
    Console.WriteLine( maxi2);
}
 
// Driver code
public static void Main()
{
    int []arr = { 1, 1, 1, 0, 0, 1, 1 };
    int n = arr.Length;
     
    FindMax(arr, n);
}
}
 
// This code is contributed by Stream_Cipher

<script>
 
// JavaScript program to implement
// the above approach
 
// Function to find maximum
// and second maximum length
function FindMax(arr, N)
{
      
    // Initialise maximum length
    let maxi = -1;
  
    // Initialise second maximum length
    let maxi2 = -1;
  
    // Initialise count
    let count = 0;
  
    // Iterate over the array
    for(let i = 0; i < N; ++i)
    {
          
        // If sequence ends
        if (arr[i] == 0)
  
            // Reset count
            count = 0;
  
        // Otherwise
        else
        {
              
            // Increase length
            // of current sequence
            count++;
  
            // Update maximum
            maxi = Math.max(maxi, count);
        }
    }
  
    // Traverse the given array
    for(let i = 0; i < N; i++)
    {
          
        // If sequence continues
        if (arr[i] == 1)
        {
              
            // Increase length
            // of current sequence
            count++;
  
            // Update second max
            if (count > maxi2 &&
                count < maxi)
            {
                maxi2 = count;
            }
        }
          
        // Reset count when 0 is found
        if (arr[i] == 0)
            count = 0;
    }
  
    maxi = Math.max(maxi, 0);
    maxi2 = Math.max(maxi2, 0);
  
    // Print the result
    document.write( maxi2);
}
 
// Driver code
 
    let arr = [ 1, 1, 1, 0, 0, 1, 1 ];
    let n = arr.length;
      
    FindMax(arr, n);
      
     // This code is contributed by target_2.
</script>

2

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