Dynamic Programming – Página 3

Subsecuencia de suma máxima de cualquier tamaño que es decreciente-creciente alternativamente

julio 5, 2022 Rudeus Greyrat

Dada una array de enteros arr[] , encuentre la subsecuencia con suma máxima cuyos elementos primero disminuyen, luego aumentan o viceversa. La subsecuencia puede comenzar en cualquier parte de la secuencia principal, no necesariamente en el primer elemento de la secuencia principal. Una secuencia {x1, x2, .. xn} es una secuencia alterna si sus elementos … Continue reading «Subsecuencia de suma máxima de cualquier tamaño que es decreciente-creciente alternativamente»

Maximiza la suma de elementos arr[i] seleccionados saltando índice por valor i

julio 5, 2022 Rudeus Greyrat

Dada una array arr[] , la tarea es calcular la suma máxima de elementos de la array de modo que, si se elige un i-ésimo elemento, entonces arr[i] se agrega a la suma y los saltos i se adelantan desde el índice actual . Ejemplos : Entrada: N = 5, arr[] = {7, 3, 1, … Continue reading «Maximiza la suma de elementos arr[i] seleccionados saltando índice por valor i»

Subsecuencia no decreciente más larga que tiene una diferencia entre elementos adyacentes menor que D

julio 5, 2022 Rudeus Greyrat

Dada una array arr[] de N enteros y un entero D , la tarea es encontrar la longitud de la subsecuencia no decreciente más larga tal que la diferencia entre cada elemento adyacente sea menor que D. Ejemplos: Entrada: arr[] = {1, 3, 2, 4, 5}, D = 2 Salida: 3 Explicación: Considere la subsecuencia … Continue reading «Subsecuencia no decreciente más larga que tiene una diferencia entre elementos adyacentes menor que D»

Maximice la suma de los números seleccionados de una array para dejarla vacía

julio 5, 2022 Rudeus Greyrat

Dada una array A[] de N números, necesitamos maximizar la suma de los números seleccionados siguiendo la operación dada: En cada paso, debe seleccionar un número A i , eliminar una ocurrencia y agregarla a la suma. Elimine una ocurrencia de A i -1 y A i +1 (si existen en la array). Repita estos … Continue reading «Maximice la suma de los números seleccionados de una array para dejarla vacía»

Subarreglo contiguo de suma más grande – Part 1

julio 5, 2022 Rudeus Greyrat

Escriba un programa eficiente para encontrar la suma del subarreglo contiguo dentro de un arreglo unidimensional de números que tenga la suma más grande. C++ // C++ program to print largest contiguous array sum #include<iostream> #include<climits> using namespace std; int maxSubArraySum(int a[], int size) { int max_so_far = INT_MIN, max_ending_here = 0; … Continue reading «Subarreglo contiguo de suma más grande – Part 1»

Subsecuencia creciente más larga | DP-3 – Part 1

julio 5, 2022 Rudeus Greyrat

Ya hemos discutido los subproblemas superpuestos y las propiedades de la subestructura óptima . Ahora, analicemos el problema de la subsecuencia creciente más larga (LIS) como un problema de ejemplo que se puede resolver mediante la programación dinámica. El problema de la subsecuencia creciente más larga (LIS) es encontrar la longitud de la subsecuencia más larga … Continue reading «Subsecuencia creciente más larga | DP-3 – Part 1»

Partición de un conjunto en K subconjuntos con igual suma usando BitMask y DP

julio 5, 2022 Rudeus Greyrat

Dada una array de enteros arr[] que consta de N enteros, la tarea es verificar si es posible dividir la array dada en K subconjuntos no vacíos de igual suma, de modo que cada elemento de la array sea parte de un solo subconjunto. Ejemplos: Entrada: arr[] = {2, 1, 4, 5, 6}, K = … Continue reading «Partición de un conjunto en K subconjuntos con igual suma usando BitMask y DP»

Función de Ackermann usando programación dinámica

julio 5, 2022 Rudeus Greyrat

Dados dos enteros M y N distintos de cero , el problema es calcular el resultado de la función de Ackermann en función de algunas ecuaciones particulares. La función de Ackermann se define como: Ejemplos: Entrada: M = 2, N = 2 Salida: 7 Entrada: M = 2, N = 7 Salida: 6141004759 Mesa vacía … Continue reading «Función de Ackermann usando programación dinámica»

Número de formas de dividir una array en K sub-arrays de igual suma

julio 5, 2022 Rudeus Greyrat

Dado un entero K y una array arr[] de N enteros, la tarea es encontrar el número de formas de dividir la array en K sub-arrays de igual suma de longitudes distintas de cero. Ejemplos: Entrada: arr[] = {0, 0, 0, 0}, K = 3 Salida: 3 Todas las formas posibles son: {{0}, {0}, {0, … Continue reading «Número de formas de dividir una array en K sub-arrays de igual suma»

Algoritmo Cocke-Younger-Kasami (CYK)

julio 5, 2022 Rudeus Greyrat

La gramática denota las reglas sintácticas para la conversación en lenguaje natural. Pero en la teoría del lenguaje formal, la gramática se define como un conjunto de reglas que pueden generar strings. El conjunto de todas las strings que se pueden generar a partir de una gramática se denomina lenguaje de la gramática. Gramática Libre … Continue reading «Algoritmo Cocke-Younger-Kasami (CYK)»