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»
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»
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»
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»
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»
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»
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)»
Dada una array arr[] de longitud N , la tarea es maximizar la suma de todos los elementos de la array realizando las siguientes operaciones como máximo una vez. Elija un prefijo de la array y multiplique todos los elementos por -1. Elija un sufijo de la array y multiplique todos los elementos por -1. … Continue reading «Maximice la suma de la array después de multiplicar un prefijo y un sufijo por -1»
Dados dos enteros positivos N y C . Hay una array de 2*N donde cada celda de la array se puede colorear en 0 o 1. La tarea es encontrar varias formas, la array de 2*N se forma teniendo exactamente c componentes. Se dice que una celda está en el mismo componente que otra celda … Continue reading «Número de formas de hacer exactamente componentes C en una array de 2*N»
Dada una array arr[] de tamaño N > 1 . La tarea es encontrar el GCD máximo posible de la array reemplazando como máximo un elemento. Ejemplos: Entrada: arr[] = {6, 7, 8} Salida: 2 Reemplace 7 con 2 y mcd(6, 2, 8) = 2, que es el máximo posible. Entrada: arr[] = {12, 18, … Continue reading «Máximo GCD posible después de reemplazar como máximo un elemento en la array dada»