Subsecuencia de paridad alternativa más larga

Dada una array a de tamaño N . La tarea es imprimir la longitud de la subsecuencia alternativa impar/par o par/impar más larga. 
Ejemplos: 
 

Entrada: a[] = { 13, 16, 8, 9, 32, 10 } 
Salida:
{13, 16, 9, 10} o cualquier otra subsecuencia de longitud 4 puede ser la respuesta. 
Entrada: a[] = {1, 2, 3, 3, 9} 
Salida:
 

Enfoque : La respuesta a la subsecuencia de paridad alternativa más larga será [impar, par, impar, par, …..] o [par, impar, par, impar, ….] secuencia. Por lo tanto, itere en la array y primero encuentre la subsecuencia impar/par más larga y luego la secuencia par/impar más larga. Los pasos para encontrar la subsecuencia más larga son: 
 

  • Iterar y encontrar el siguiente número impar y aumentar la longitud.
  • Iterar y encontrar el siguiente número impar y aumentar la longitud.
  • Repita el paso 1 y el paso 2 alternativamente comenzando desde el paso 1 hasta el final para encontrar la subsecuencia impar/par más larga.
  • Repita el paso 1 y el paso 2 alternativamente comenzando desde el paso 2 hasta el final para encontrar la subsecuencia par/impar más larga.

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

C++

// C++ program to find the length
// of the longest alternative parity
// subsequence
#include <iostream>
using namespace std;
 
// Function to find the longest
int longestAlternativeSequence(int a[], int n)
{
    int maxi1 = 0;
 
    // Marks the starting of odd
    // number as sequence and
    // alternatively changes
    int f1 = 0;
 
    // Finding the longest odd/even sequence
    for (int i = 0; i < n; i++) {
 
        // Find odd number
        if (!f1) {
            if (a[i] % 2) {
                f1 = 1;
                maxi1++;
            }
        }
 
        // Find even number
        else {
            if (a[i] % 2 == 0) {
                maxi1++;
                f1 = 0;
            }
        }
    }
 
    int maxi2 = 0;
    int f2 = 0;
 
    // Length of the longest even/odd sequence
    for (int i = 0; i < n; i++) {
 
        // Find odd number
        if (f2) {
            if (a[i] % 2) {
                f2 = 1;
                maxi2++;
            }
        }
 
        // Find even number
        else {
            if (a[i] % 2 == 0) {
                maxi2++;
                f2 = 0;
            }
        }
    }
 
    // Answer is maximum of both
    // odd/even or even/odd subsequence
    return max(maxi1, maxi2);
}
 
// Driver Code
int main()
{
    int a[] = { 13, 16, 8, 9, 32, 10 };
    int n = sizeof(a) / sizeof(a[0]);
    cout << longestAlternativeSequence(a, n);
}

Java

// Java program to find the length
// of the longest alternative parity
// subsequence
class GFG
{
 
// Function to find the longest
static int longestAlternativeSequence(int a[], int n)
{
    int maxi1 = 0;
 
    // Marks the starting of odd
    // number as sequence and
    // alternatively changes
    int f1 = 0;
 
    // Finding the longest odd/even sequence
    for (int i = 0; i < n; i++)
    {
 
        // Find odd number
        if (f1 % 2 != 0)
        {
            if (a[i] % 2 == 1)
            {
                f1 = 1;
                maxi1++;
            }
        }
 
        // Find even number
        else
        {
            if (a[i] % 2 == 0)
            {
                maxi1++;
                f1 = 0;
            }
        }
    }
 
    int maxi2 = 0;
    int f2 = 0;
 
    // Length of the longest even/odd sequence
    for (int i = 0; i < n; i++)
    {
 
        // Find odd number
        if (f2 % 2 != 0)
        {
            if (a[i] % 2 == 1)
            {
                f2 = 1;
                maxi2++;
            }
        }
 
        // Find even number
        else
        {
            if (a[i] % 2 == 0)
            {
                maxi2++;
                f2 = 0;
            }
        }
    }
 
    // Answer is maximum of both
    // odd/even or even/odd subsequence
    return Math.max(maxi1, maxi2);
}
 
// Driver Code
public static void main(String[] args)
{
    int a[] = { 13, 16, 8, 9, 32, 10 };
    int n = a.length;
    System.out.println(longestAlternativeSequence(a, n));
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 program to find the length
# of the longest alternative parity
# subsequence
 
# Function to find the longest
def longestAlternativeSequence(a, n):
    maxi1 = 0
 
    # Marks the starting of odd
    # number as sequence and
    # alternatively changes
    f1 = 0
 
    # Finding the longest odd/even sequence
    for i in range(n):
 
        # Find odd number
        if (f1 == 0):
            if (a[i] % 2):
                f1 = 1
                maxi1 += 1
 
        # Find even number
        else:
            if (a[i] % 2 == 0):
                maxi1 += 1
                f1 = 0
                 
    maxi2 = 0
    f2 = 0
 
    # Length of the longest even/odd sequence
    for i in range(n):
 
        # Find odd number
        if (f2):
            if (a[i] % 2):
                f2 = 1
                maxi2 += 1
 
        # Find even number
        else:
            if (a[i] % 2 == 0):
                maxi2 += 1
                f2 = 0
 
    # Answer is maximum of both
    # odd/even or even/odd subsequence
    return max(maxi1, maxi2)
 
# Driver Code
a = [13, 16, 8, 9, 32, 10]
n = len(a)
print(longestAlternativeSequence(a, n))
 
# This code is contributed by Mohit Kumar

C#

// C# program to find the length
// of the longest alternative parity
// subsequence
using System;
 
class GFG
{
     
// Function to find the longest
static int longestAlternativeSequence(int []a,
                                      int n)
{
    int maxi1 = 0;
 
    // Marks the starting of odd
    // number as sequence and
    // alternatively changes
    int f1 = 0;
 
    // Finding the longest odd/even sequence
    for (int i = 0; i < n; i++)
    {
 
        // Find odd number
        if (f1 != 0)
        {
            if (a[i] % 2 == 0)
            {
                f1 = 1;
                maxi1++;
            }
        }
 
        // Find even number
        else
        {
            if (a[i] % 2 == 0)
            {
                maxi1++;
                f1 = 0;
            }
        }
    }
 
    int maxi2 = 0;
    int f2 = 0;
 
    // Length of the longest even/odd sequence
    for (int i = 0; i < n; i++)
    {
 
        // Find odd number
        if (f2 == 0)
        {
            if (a[i] % 2 == 0)
            {
                f2 = 1;
                maxi2++;
            }
        }
 
        // Find even number
        else
        {
            if (a[i] % 2 == 0)
            {
                maxi2++;
                f2 = 0;
            }
        }
    }
 
    // Answer is maximum of both
    // odd/even or even/odd subsequence
    return Math.Max(maxi1, maxi2);
}
 
// Driver Code
public static void Main()
{
    int []a = { 13, 16, 8, 9, 32, 10 };
    int n = a.Length;
    Console.Write(longestAlternativeSequence(a, n));
}
}
 
// This code is contributed by Nidhi

Javascript

<script>
 
// Javascript program to find the length
// of the longest alternative parity
// subsequence
 
// Function to find the longest
function longestAlternativeSequence(a, n)
{
    let maxi1 = 0;
 
    // Marks the starting of odd
    // number as sequence and
    // alternatively changes
    let f1 = 0;
 
    // Finding the longest odd/even sequence
    for (let i = 0; i < n; i++) {
 
        // Find odd number
        if (!f1) {
            if (a[i] % 2) {
                f1 = 1;
                maxi1++;
            }
        }
 
        // Find even number
        else {
            if (a[i] % 2 == 0) {
                maxi1++;
                f1 = 0;
            }
        }
    }
 
    let maxi2 = 0;
    let f2 = 0;
 
    // Length of the longest even/odd sequence
    for (let i = 0; i < n; i++) {
 
        // Find odd number
        if (f2) {
            if (a[i] % 2) {
                f2 = 1;
                maxi2++;
            }
        }
 
        // Find even number
        else {
            if (a[i] % 2 == 0) {
                maxi2++;
                f2 = 0;
            }
        }
    }
 
    // Answer is maximum of both
    // odd/even or even/odd subsequence
    return Math.max(maxi1, maxi2);
}
 
// Driver Code
    let a = [ 13, 16, 8, 9, 32, 10 ];
    let n = a.length;
    document.write(longestAlternativeSequence(a, n));
 
</script>
Producción: 

4

 

Complejidad de tiempo – O(n), ya que corre un ciclo de 0 a (n – 1).

Espacio Auxiliar – O(1), ya que no se ha ocupado ningún espacio extra.

Publicación traducida automáticamente

Artículo escrito por Striver y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *