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: 4
{13, 16, 9, 10} o cualquier otra subsecuencia de longitud 4 puede ser la respuesta.
Entrada: a[] = {1, 2, 3, 3, 9}
Salida: 3
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.