Dada una array binaria, encuentre la longitud de la subsecuencia más larga tal que no haya 0 después de 1.
Ejemplos:
Input : 1 1 0 1 Output : 3 Explanation : If we remove 0 from the array, then no zero comes right after one (satisfying the condition) and the maximum game left are 3 (i.e. 1 1 1) Input : 0 Output : 1 Explanation : Since he wants to save maximum game in the array. He doesn't remove any game.
Averigüemos cuántos ceros habrá en esta secuencia y luego tomemos todos los que vienen después del último cero. En cada paso, tome el siguiente cero desde el comienzo de la secuencia y cuente los que le siguen. Actualice la respuesta con el valor máximo.
Puede precalcular el número de unos en el sufijo.
Por ejemplo, 0 1 0 0 1 1 1
Después de calcular el sufijo, la array se convierte en:
0 4 0 0 3 2 1
Muévase de principio a fin y cada vez que se encuentre cero en la array, aumente el número de ceros en 1. Si la array [índice] no es cero, entonces res = max (res, número de ceros + valor de la array en ese índice).
Y luego, después del bucle: res = max(res, numberofzeros)
Implementación:
C++
// CPP program to find longest subsequence
// such that there is no 0 after 1.
#include <bits/stdc++.h>
using namespace std;
int maxSubseq(int vec[], int n) {
// Store the count of number of ones
// from right to left in the array
int suffix = 0;
for (int i = n - 1; i >= 0; i--)
{
if (vec[i] == 1)
{
suffix++;
vec[i] = suffix;
}
}
// Traverse from left to right, keep count
// of 0s and for every 0, check number of
// 1s after it. Update the result if needed.
int res = 0;
int zero = 0;
for (int i = 0; i < n; i++)
{
if (vec[i] == 0)
zero++;
// Checking the maximum size
if (vec[i] > 0)
res = max(res, zero + vec[i]);
}
// Checking the maximum size
return max(res, zero);
}
// Driver Code
int main()
{
int input[] = { 0, 1, 0, 0, 1, 0 };
int n = sizeof(input) / sizeof(input[0]);
cout << maxSubseq(input, n);
return 0;
}
Java
// java program to find longest subsequence
// such that there is no 0 after 1.
import java.io.*;
public class GFG {
static int maxSubseq(int []vec, int n)
{
// Store the count of number of
// ones from right to left in
// the array
int suffix = 0;
for (int i = n - 1; i >= 0; i--)
{
if (vec[i] == 1)
{
suffix++;
vec[i] = suffix;
}
}
// Traverse from left to right, keep
// count of 0s and for every 0, check
// number of 1s after it. Update the
// result if needed.
int res = 0;
int zero = 0;
for (int i = 0; i < n; i++)
{
if (vec[i] == 0)
zero++;
// Checking the maximum size
if (vec[i] > 0)
res = Math.max(res, zero + vec[i]);
}
// Checking the maximum size
return Math.max(res, zero);
}
// Driver Code
static public void main (String[] args)
{
int []input = { 0, 1, 0, 0, 1, 0 };
int n = input.length;
System.out.println(maxSubseq(input, n));
}
}
// This code is contributed by vt_m.
Python3
# Python 3 program to find longest subsequence # such that there is no 0 after 1. def maxSubseq(vec, n): # Store the count of number of ones # from right to left in the array suffix = 0 i = n-1 while(i >= 0): if (vec[i] == 1): suffix += 1 vec[i] = suffix i -= 1 # Traverse from left to right, keep count # of 0s and for every 0, check number of # 1s after it. Update the result if needed. res = 0 zero = 0 for i in range(0,n,1): if (vec[i] == 0): zero += 1 # Checking the maximum size if (vec[i] > 0): res = max(res, zero + vec[i]) # Checking the maximum size return max(res, zero) # Driver code if __name__ == '__main__': input = [0, 1, 0, 0, 1, 0] n = len(input) print(maxSubseq(input, n)) # This code is contributed by # Surendra_Gangwar
C#
// C# program to find longest subsequence
// such that there is no 0 after 1.
using System;
public class GFG {
static int maxSubseq(int []vec, int n)
{
// Store the count of number of
// ones from right to left in
// the array
int suffix = 0;
for (int i = n - 1; i >= 0; i--)
{
if (vec[i] == 1)
{
suffix++;
vec[i] = suffix;
}
}
// Traverse from left to right, keep
// count of 0s and for every 0, check
// number of 1s after it. Update the
// result if needed.
int res = 0;
int zero = 0;
for (int i = 0; i < n; i++)
{
if (vec[i] == 0)
zero++;
// Checking the maximum size
if (vec[i] > 0)
res = Math.Max(res, zero + vec[i]);
}
// Checking the maximum size
return Math.Max(res, zero);
}
// Driver Code
static public void Main ()
{
int []input = { 0, 1, 0, 0, 1, 0 };
int n = input.Length;
Console.WriteLine(maxSubseq(input, n));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to find longest
// subsequence such that there
// is no 0 after 1.
function maxSubseq($vec, $n)
{
// Store the count of
// number of ones from
// right to left in
// the array
$suffix = 0;
for ($i = $n - 1;
$i >= 0; $i--)
{
if ($vec[$i] == 1)
{
$suffix++;
$vec[$i] = $suffix;
}
}
// Traverse from left to
// right, keep count of
// 0s and for every 0,
// check number of 1s after
// it. Update the result if
// needed.
$res = 0;
$zero = 0;
for ($i = 0; $i < $n; $i++)
{
if ($vec[$i] == 0)
$zero++;
// Checking the
// maximum size
if ($vec[$i] > 0)
$res = max($res, $zero +
$vec[$i]);
}
// Checking the
// maximum size
return max($res, $zero);
}
// Driver Code
$input = array(0, 1, 0, 0, 1, 0);
$n = count($input);
echo maxSubseq($input, $n);
// This code is contributed
// by anuj_67.
?>
Javascript
<script>
// Javascript program to find longest subsequence
// such that there is no 0 after 1.
function maxSubseq(vec, n)
{
// Store the count of number of
// ones from right to left in
// the array
let suffix = 0;
for (let i = n - 1; i >= 0; i--)
{
if (vec[i] == 1)
{
suffix++;
vec[i] = suffix;
}
}
// Traverse from left to right, keep
// count of 0s and for every 0, check
// number of 1s after it. Update the
// result if needed.
let res = 0;
let zero = 0;
for (let i = 0; i < n; i++)
{
if (vec[i] == 0)
zero++;
// Checking the maximum size
if (vec[i] > 0)
res = Math.max(res, zero + vec[i]);
}
// Checking the maximum size
return Math.max(res, zero);
}
let input = [ 0, 1, 0, 0, 1, 0 ];
let n = input.length;
document.write(maxSubseq(input, n));
</script>
Producción
4
Este artículo es una contribución de Sachin Bisht . 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 review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA