Dada una string binaria S de tamaño N , la tarea es encontrar la longitud de la subsecuencia no creciente más larga en la string S dada .
Ejemplos:
Entrada: S = “0101110110100001011”
Salida: 12
Explicación: La subsecuencia no creciente más larga es “111111100000”, con una longitud igual a 12.Entrada: S = 10101
Salida: 3
Enfoque: El problema dado se puede resolver basándose en la observación de que la string S es una string binaria, por lo que una subsecuencia no creciente siempre constará de 0 con más 1 consecutivos o 1 con más 0 consecutivos . Siga los pasos a continuación para resolver el problema:
- Inicialice una array , digamos pre[] , que almacene el número de 1 hasta que cada índice i for i esté sobre el rango [0, N – 1] .
- Inicialice una array , digamos post[] , que almacene el número de 0 hasta cada índice i hasta el final de la string para i sobre el rango [0, N – 1] .
- Inicialice una variable, digamos ans , que almacene la longitud de la subsecuencia no creciente más larga en la string S dada .
- Iterar sobre el rango [0, N – 1] y actualizar el valor de ans al máximo de ans y (pre[i] + post[i]) .
- Después de completar los pasos anteriores, imprima el valor de ans como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the length of the
// longest non-increasing subsequence
int findLength(string str, int n)
{
// Stores the prefix and suffix
// count of 1s and 0s respectively
int pre[n], post[n];
// Initialize the array
memset(pre, 0, sizeof(pre));
memset(post, 0, sizeof(post));
// Store the number of '1's
// up to current index i in pre
for (int i = 0; i < n; i++) {
// Find the prefix sum
if (i != 0) {
pre[i] += pre[i - 1];
}
// If the current element
// is '1', update the pre[i]
if (str[i] == '1') {
pre[i] += 1;
}
}
// Store the number of '0's over
// the range [i, N - 1]
for (int i = n - 1; i >= 0; i--) {
// Find the suffix sum
if (i != n - 1)
post[i] += post[i + 1];
// If the current element
// is '0', update post[i]
if (str[i] == '0')
post[i] += 1;
}
// Stores the maximum length
int ans = 0;
// Find the maximum value of
// pre[i] + post[i]
for (int i = 0; i < n; i++) {
ans = max(ans, pre[i] + post[i]);
}
// Return the answer
return ans;
}
// Driver Code
int main()
{
string S = "0101110110100001011";
cout << findLength(S, S.length());
return 0;
}
Java
// Java program for the above approach
class GFG{
// Function to find the length of the
// longest non-increasing subsequence
static int findLength(String str, int n)
{
// Stores the prefix and suffix
// count of 1s and 0s respectively
int pre[] = new int[n];
int post[] = new int[n];
// Initialize the array
for(int i = 0; i < n; i++)
{
pre[i] = 0;
post[i] = 0;
}
// Store the number of '1's
// up to current index i in pre
for(int i = 0; i < n; i++)
{
// Find the prefix sum
if (i != 0)
{
pre[i] += pre[i - 1];
}
// If the current element
// is '1', update the pre[i]
if (str.charAt(i) == '1')
{
pre[i] += 1;
}
}
// Store the number of '0's over
// the range [i, N - 1]
for(int i = n - 1; i >= 0; i--)
{
// Find the suffix sum
if (i != n - 1)
post[i] += post[i + 1];
// If the current element
// is '0', update post[i]
if (str.charAt(i) == '0')
post[i] += 1;
}
// Stores the maximum length
int ans = 0;
// Find the maximum value of
// pre[i] + post[i]
for(int i = 0; i < n; i++)
{
ans = Math.max(ans, pre[i] + post[i]);
}
// Return the answer
return ans;
}
// Driver Code
public static void main(String[] args)
{
String S = "0101110110100001011";
System.out.println(findLength(S, S.length()));
}
}
// This code is contributed by abhinavjain194
Python3
# Python3 program for the above approach # Function to find the length of the # longest non-increasing subsequence def findLength(str, n): # Stores the prefix and suffix # count of 1s and 0s respectively pre = [0] * n post = [0] * n # Store the number of '1's # up to current index i in pre for i in range(n): # Find the prefix sum if (i != 0): pre[i] += pre[i - 1] # If the current element # is '1', update the pre[i] if (str[i] == '1'): pre[i] += 1 # Store the number of '0's over # the range [i, N - 1] for i in range(n - 1, -1, -1): # Find the suffix sum if (i != (n - 1)): post[i] += post[i + 1] # If the current element # is '0', update post[i] if (str[i] == '0'): post[i] += 1 # Stores the maximum length ans = 0 # Find the maximum value of # pre[i] + post[i] for i in range(n): ans = max(ans, pre[i] + post[i]) # Return the answer return ans # Driver Code S = "0101110110100001011" n = len(S) print(findLength(S, n)) # This code is contributed by susmitakundugoaldanga
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the length of the
// longest non-increasing subsequence
static int findLength(String str, int n)
{
// Stores the prefix and suffix
// count of 1s and 0s respectively
int []pre = new int[n];
int []post = new int[n];
// Initialize the array
for(int i = 0; i < n; i++)
{
pre[i] = 0;
post[i] = 0;
}
// Store the number of '1's
// up to current index i in pre
for(int i = 0; i < n; i++)
{
// Find the prefix sum
if (i != 0)
{
pre[i] += pre[i - 1];
}
// If the current element
// is '1', update the pre[i]
if (str[i] == '1')
{
pre[i] += 1;
}
}
// Store the number of '0's over
// the range [i, N - 1]
for(int i = n - 1; i >= 0; i--)
{
// Find the suffix sum
if (i != n - 1)
post[i] += post[i + 1];
// If the current element
// is '0', update post[i]
if (str[i] == '0')
post[i] += 1;
}
// Stores the maximum length
int ans = 0;
// Find the maximum value of
// pre[i] + post[i]
for(int i = 0; i < n; i++)
{
ans = Math.Max(ans, pre[i] + post[i]);
}
// Return the answer
return ans;
}
// Driver Code
public static void Main(String[] args)
{
String S = "0101110110100001011";
Console.WriteLine(findLength(S, S.Length));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program for the above approach
// Function to find the length of the
// longest non-increasing subsequence
function findLength(str, n)
{
// Stores the prefix and suffix
// count of 1s and 0s respectively
let pre = Array.from({length: n}, (_, i) => 0);
let post = Array.from({length: n}, (_, i) => 0);
// Initialize the array
for(let i = 0; i < n; i++)
{
pre[i] = 0;
post[i] = 0;
}
// Store the number of '1's
// up to current index i in pre
for(let i = 0; i < n; i++)
{
// Find the prefix sum
if (i != 0)
{
pre[i] += pre[i - 1];
}
// If the current element
// is '1', update the pre[i]
if (str[i] == '1')
{
pre[i] += 1;
}
}
// Store the number of '0's over
// the range [i, N - 1]
for(let i = n - 1; i >= 0; i--)
{
// Find the suffix sum
if (i != n - 1)
post[i] += post[i + 1];
// If the current element
// is '0', update post[i]
if (str[i] == '0')
post[i] += 1;
}
// Stores the maximum length
let ans = 0;
// Find the maximum value of
// pre[i] + post[i]
for(let i = 0; i < n; i++)
{
ans = Math.max(ans, pre[i] + post[i]);
}
// Return the answer
return ans;
}
// Driver Code
let S = "0101110110100001011";
document.write(findLength(S, S.length));
</script>
Producción:
12
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por aniket173000 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA