Dada una array binaria arr[] , la tarea es encontrar la longitud máxima posible de la subsecuencia no decreciente que se puede generar invirtiendo una subarreglo como máximo una vez.
Ejemplos:
Entrada: array[] = {0, 1, 0, 1}
Salida: 4
Explicación:
Después de invertir el subarreglo del índice [2, 3], el arreglo se modifica a {0, 0, 1, 1}.
Por lo tanto, la subsecuencia no decreciente más larga es {0, 0, 1, 1}.Entrada: arr[] = {0, 1, 1, 1, 0, 0, 1, 1, 0}
Salida: 9
Explicación:
después de invertir el subarreglo del índice [2, 6], el arreglo se modifica a {0, 0 , 0, 1, 1, 1, 1, 1, 0}.
Por lo tanto, la subsecuencia no decreciente más larga es {0, 0, 0, 1, 1, 1, 1, 1}.
Enfoque ingenuo: el enfoque más simple para resolver el problema es invertir cada subarreglo posible en el arreglo dado y encontrar la subsecuencia no decreciente más larga posible del arreglo después de invertir el subarreglo.
Complejidad Temporal: O(N 3 )
Espacio Auxiliar: O(N)
Enfoque Eficiente: La idea es utilizar Programación Dinámica para resolver el problema. Siga los pasos a continuación:
- Dado que el arreglo es un arreglo binario, la idea es encontrar la subsecuencia más larga entre las subsecuencias de las formas {0….0} , {0…1…} , {0..1..0…}, 0..1 ..0..1 .
- Inicialice una tabla de programación dinámica como dp[][] que almacena lo siguiente:
dp[i][0] : Almacena la longitud de la subsecuencia más larga (0..) de a[0 a i].
dp[i][1] : Almacena la longitud de la subsecuencia más larga (0..1..) de a[0 a i].
dp[i][2] : Almacena la longitud de la subsecuencia más larga (0..1..0..) de a[0 a i].
dp[i][3] : Almacena la longitud de la subsecuencia más larga (0..1..0..1..) de a[0 a i].
- Por lo tanto, la respuesta es la subsecuencia más larga o el máximo de las 4 posibilidades dadas ( dp[n-1][0], d[n-1][1], dp[n-1][2], dp[ n-1][3] ) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include<bits/stdc++.h>
using namespace std;
// Function to find the maximum length
// non decreasing subarray by reversing
// at most one subarray
void main_fun(int arr[], int n)
{
// dp[i][j] be the longest
// subsequence of a[0...i]
// with first j parts
int dp[4][n];
memset(dp, 0, sizeof(dp[0][0] * 4 * n));
if (arr[0] == 0)
dp[0][0] = 1;
else
dp[1][0] = 1;
// Maximum length sub-sequence
// of (0..)
for(int i = 1; i < n; i++)
{
if (arr[i] == 0)
dp[0][i] = dp[0][i - 1] + 1;
else
dp[0][i] = dp[0][i - 1];
}
// Maximum length sub-sequence
// of (0..1..)
for(int i = 1; i < n; i++)
{
if (arr[i] == 1)
dp[1][i] = max(dp[1][i - 1] + 1,
dp[0][i - 1] + 1);
else
dp[1][i] = dp[1][i - 1];
}
// Maximum length sub-sequence
// of (0..1..0..)
for(int i = 1; i < n; i++)
{
if (arr[i] == 0)
{
dp[2][i] = max(dp[2][i - 1] + 1,
max(dp[1][i - 1] + 1,
dp[0][i - 1] + 1));
}
else
dp[2][i] = dp[2][i - 1];
}
// Maximum length sub-sequence
// of (0..1..0..1..)
for(int i = 1; i < n; i++)
{
if (arr[i] == 1)
{
dp[3][i] = max(dp[3][i - 1] + 1,
max(dp[2][i - 1] + 1,
max(dp[1][i - 1] + 1,
dp[0][i - 1] + 1)));
}
else
dp[3][i] = dp[3][i - 1];
}
// Find the max length subsequence
int ans = max(dp[2][n - 1], max(dp[1][n - 1],
max(dp[0][n - 1], dp[3][n - 1])));
// Print the answer
cout << (ans);
}
// Driver Code
int main()
{
int n = 4;
int arr[] = {0, 1, 0, 1};
main_fun(arr, n);
return 0;
}
// This code is contributed by chitranayal
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to find the maximum length
// non decreasing subarray by reversing
// at most one subarray
static void main_fun(int arr[], int n)
{
// dp[i][j] be the longest
// subsequence of a[0...i]
// with first j parts
int[][] dp = new int[4][n];
if (arr[0] == 0)
dp[0][0] = 1;
else
dp[1][0] = 1;
// Maximum length sub-sequence
// of (0..)
for(int i = 1; i < n; i++)
{
if (arr[i] == 0)
dp[0][i] = dp[0][i - 1] + 1;
else
dp[0][i] = dp[0][i - 1];
}
// Maximum length sub-sequence
// of (0..1..)
for(int i = 1; i < n; i++)
{
if (arr[i] == 1)
dp[1][i] = Math.max(dp[1][i - 1] + 1,
dp[0][i - 1] + 1);
else
dp[1][i] = dp[1][i - 1];
}
// Maximum length sub-sequence
// of (0..1..0..)
for(int i = 1; i < n; i++)
{
if (arr[i] == 0)
{
dp[2][i] = Math.max(dp[2][i - 1] + 1,
Math.max(dp[1][i - 1] + 1,
dp[0][i - 1] + 1));
}
else
dp[2][i] = dp[2][i - 1];
}
// Maximum length sub-sequence
// of (0..1..0..1..)
for(int i = 1; i < n; i++)
{
if (arr[i] == 1)
{
dp[3][i] = Math.max(dp[3][i - 1] + 1,
Math.max(dp[2][i - 1] + 1,
Math.max(dp[1][i - 1] + 1,
dp[0][i - 1] + 1)));
}
else
dp[3][i] = dp[3][i - 1];
}
// Find the max length subsequence
int ans = Math.max(dp[2][n - 1],
Math.max(dp[1][n - 1],
Math.max(dp[0][n - 1],
dp[3][n - 1])));
// Print the answer
System.out.print(ans);
}
// Driver code
public static void main (String[] args)
{
int n = 4;
int arr[] = { 0, 1, 0, 1 };
main_fun(arr, n);
}
}
// This code is contributed by offbeat
Python3
# Python3 program to implement # the above approach import sys # Function to find the maximum length # non decreasing subarray by reversing # at most one subarray def main(arr, n): # dp[i][j] be the longest # subsequence of a[0...i] # with first j parts dp = [[0 for x in range(n)] for y in range(4)] if arr[0] == 0: dp[0][0] = 1 else: dp[1][0] = 1 # Maximum length sub-sequence # of (0..) for i in range(1, n): if arr[i] == 0: dp[0][i] = dp[0][i-1] + 1 else: dp[0][i] = dp[0][i-1] # Maximum length sub-sequence # of (0..1..) for i in range(1, n): if arr[i] == 1: dp[1][i] = max(dp[1][i-1] + 1, dp[0][i-1] + 1) else: dp[1][i] = dp[1][i-1] # Maximum length sub-sequence # of (0..1..0..) for i in range(1, n): if arr[i] == 0: dp[2][i] = max([dp[2][i-1] + 1, dp[1][i-1] + 1, dp[0][i-1] + 1]) else: dp[2][i] = dp[2][i-1] # Maximum length sub-sequence # of (0..1..0..1..) for i in range(1, n): if arr[i] == 1: dp[3][i] = max([dp[3][i-1] + 1, dp[2][i-1] + 1, dp[1][i-1] + 1, dp[0][i-1] + 1]) else: dp[3][i] = dp[3][i-1] # Find the max length subsequence ans = max([dp[2][n-1], dp[1][n-1], dp[0][n-1], dp[3][n-1]]) # Print the answer print(ans) # Driver Code if __name__ == "__main__": n = 4 arr = [0, 1, 0, 1] main(arr, n)
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to find the maximum length
// non decreasing subarray by reversing
// at most one subarray
static void main_fun(int []arr, int n)
{
// dp[i,j] be the longest
// subsequence of a[0...i]
// with first j parts
int[,] dp = new int[4, n];
if (arr[0] == 0)
dp[0, 0] = 1;
else
dp[1, 0] = 1;
// Maximum length sub-sequence
// of (0..)
for(int i = 1; i < n; i++)
{
if (arr[i] == 0)
dp[0, i] = dp[0, i - 1] + 1;
else
dp[0, i] = dp[0, i - 1];
}
// Maximum length sub-sequence
// of (0..1..)
for(int i = 1; i < n; i++)
{
if (arr[i] == 1)
dp[1, i] = Math.Max(dp[1, i - 1] + 1,
dp[0, i - 1] + 1);
else
dp[1, i] = dp[1, i - 1];
}
// Maximum length sub-sequence
// of (0..1..0..)
for(int i = 1; i < n; i++)
{
if (arr[i] == 0)
{
dp[2, i] = Math.Max(dp[2, i - 1] + 1,
Math.Max(dp[1, i - 1] + 1,
dp[0, i - 1] + 1));
}
else
dp[2, i] = dp[2, i - 1];
}
// Maximum length sub-sequence
// of (0..1..0..1..)
for(int i = 1; i < n; i++)
{
if (arr[i] == 1)
{
dp[3, i] = Math.Max(dp[3, i - 1] + 1,
Math.Max(dp[2, i - 1] + 1,
Math.Max(dp[1, i - 1] + 1,
dp[0, i - 1] + 1)));
}
else
dp[3, i] = dp[3, i - 1];
}
// Find the max length subsequence
int ans = Math.Max(dp[2, n - 1],
Math.Max(dp[1, n - 1],
Math.Max(dp[0, n - 1],
dp[3, n - 1])));
// Print the answer
Console.Write(ans);
}
// Driver code
public static void Main(String[] args)
{
int n = 4;
int []arr = { 0, 1, 0, 1 };
main_fun(arr, n);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to find the maximum length
// non decreasing subarray by reversing
// at most one subarray
function main_fun(arr, n)
{
// dp[i][j] be the longest
// subsequence of a[0...i]
// with first j parts
var dp = Array.from(Array(4), ()=>Array(n).fill(0));
if (arr[0] == 0)
dp[0][0] = 1;
else
dp[1][0] = 1;
// Maximum length sub-sequence
// of (0..)
for(var i = 1; i < n; i++)
{
if (arr[i] == 0)
dp[0][i] = dp[0][i - 1] + 1;
else
dp[0][i] = dp[0][i - 1];
}
// Maximum length sub-sequence
// of (0..1..)
for(var i = 1; i < n; i++)
{
if (arr[i] == 1)
dp[1][i] = Math.max(dp[1][i - 1] + 1,
dp[0][i - 1] + 1);
else
dp[1][i] = dp[1][i - 1];
}
// Maximum length sub-sequence
// of (0..1..0..)
for(var i = 1; i < n; i++)
{
if (arr[i] == 0)
{
dp[2][i] = Math.max(dp[2][i - 1] + 1,
Math.max(dp[1][i - 1] + 1,
dp[0][i - 1] + 1));
}
else
dp[2][i] = dp[2][i - 1];
}
// Maximum length sub-sequence
// of (0..1..0..1..)
for(var i = 1; i < n; i++)
{
if (arr[i] == 1)
{
dp[3][i] = Math.max(dp[3][i - 1] + 1,
Math.max(dp[2][i - 1] + 1,
Math.max(dp[1][i - 1] + 1,
dp[0][i - 1] + 1)));
}
else
dp[3][i] = dp[3][i - 1];
}
// Find the max length subsequence
var ans = Math.max(dp[2][n - 1], Math.max(dp[1][n - 1],
Math.max(dp[0][n - 1], dp[3][n - 1])));
// Print the answer
document.write(ans);
}
// Driver Code
var n = 4;
var arr = [0, 1, 0, 1];
main_fun(arr, n);
</script>
Producción:
4
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kfardeen7890 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA