(1) Máxima ganancia en compra-venta de acciones
Dado un arreglo precios donde precios[i] representa el precio de una acción en el día i, se permite realizar una única operación de compra seguida de una venta posterior. El objetivo es maximizar la ganancia.

ganancia_max = 0
precio_minimo = precios[0]
for precio in precios:
    ganancia_max = max(ganancia_max, precio - precio_minimo)
    precio_minimo = min(precio_minimo, precio)
return ganancia_max

(2) Alcance del salto (versión booleana)
Dado un arreglo no negativo pasos, donde pasos[i] indica la longitud máxima de salto desde la posición i, determinar si es posible alcanzar el último índice partiendo desde el índice cero.

alcance = 0
for indice in range(len(pasos)):
    if indice > alcance:
        return False
    alcance = max(alcance, indice + pasos[indice])
return True

(3) Número mínimo de saltos al final
Con las mismas reglas anteriores, calcular la cantidad mínima de saltos necesarios para llegar al último índice.

saltos = 0
limite_actual = 0
limite_siguiente = 0
for i in range(len(pasos) - 1):
    limite_siguiente = max(limite_siguiente, i + pasos[i])
    if i == limite_actual:
        saltos += 1
        limite_actual = limite_siguiente
return saltos

(4) Segmentación óptima por caracteres únicos
Dada una cadena s, dividirla en la mayor cantidad posible de segmentos tal que cada letra aparezca exclusivamente en un solo segmento. Devolver las longitudes de dichos segmentos.

ultima_posicion = {caracter: i for i, caracter in enumerate(s)}
inicio = fin = 0
segmentos = []
for i, c in enumerate(s):
    fin = max(fin, ultima_posicion[c])
    if i == fin:
        segmentos.append(fin - inicio + 1)
        inicio = i + 1
return segmentos

Programación Dinámica

(1) Escaleras con pasos unitarios o dobles
Calcular cuántas formas distintas existen para subir n escalones, si en cada movimiento se puede avanzar 1 o 2 peldaños.

if n <= 2:
    return n
prev2, prev1 = 1, 2
for _ in range(3, n + 1):
    actual = prev1 + prev2
    prev2, prev1 = prev1, actual
return actual

(2) Construcción iterativa del triángulo de Pascal
Generar las primeras filas del triángulo de Pascal, donde cada entrada es la suma de los dos valores superiores adyacentes.

triangulo = [[1] * (i + 1) for i in range(filas)]
for i in range(2, filas):
    for j in range(1, i):
        triangulo[i][j] = triangulo[i - 1][j - 1] + triangulo[i - 1][j]
return triangulo

(3) Robo óptimo sin alarmas vecinas
Dado un arreglo valores que representa el dinero en cada casa, encontrar la suma máxima que puede robarse sin activar alarmas (no se pueden robar casas contiguas).

anterior = actual = 0
for valor in valores:
    anterior, actual = actual, max(actual, anterior + valor)
return actual

(4) Variaciones del problema de la mochila
- 0-1 Mochila: cada objeto se incluye como máximo una vez.
- Mochila ilimitada: cada objeto puede usarse múltiples veces.

# 0-1 mochila: dp[i][capacidad] = max(dp[i-1][capacidad], dp[i-1][capacidad - peso[i]] + valor[i])
# Mochila ilimitada: dp[i][capacidad] = max(dp[i-1][capacidad], dp[i][capacidad - peso[i]] + valor[i])

(5) Descomposición en cuadrados perfectos
Hallar el número mínimo de cuadrados perfectos cuya suma sea igual a n.

dp = [float('inf')] * (n + 1)
dp[0] = 0
for i in range(1, n + 1):
    j = 1
    while j * j <= i:
        dp[i] = min(dp[i], dp[i - j * j] + 1)
        j += 1
return dp[n]

(6) Cambio óptimo con monedas
Dado un conjunto de denominaciones monedas y un monto monto, hallar el número mínimo de monedas necesarias para formarlo. Si no es posible, devolver −1.

dp = [float('inf')] * (monto + 1)
dp[0] = 0
for moneda in monedas:
    for j in range(moneda, monto + 1):
        dp[j] = min(dp[j], dp[j - moneda] + 1)
return dp[monto] if dp[monto] != float('inf') else -1

(7) Validación de segmentación léxica
Determinar si una cadena s puede descomponerse en palabras presentes en un diccionario diccionario, permitiendo repeticiones.

n = len(s)
valido = [False] * (n + 1)
valido[0] = True
for i in range(n):
    if not valido[i]:
        continue
    for j in range(i + 1, n + 1):
        if s[i:j] in diccionario:
            valido[j] = True
return valido[n]

(8) Subsecuencia creciente más larga (LIS)
Encnotrar la longitud de la subsecuencia estrictamente creciente más larga dentro de un arreglo numeros.

n = len(numeros)
longitud = [1] * n
for i in range(n):
    for j in range(i):
        if numeros[i] > numeros[j]:
            longitud[i] = max(longitud[i], longitud[j] + 1)
return max(longitud) if n > 0 else 0

(9) Subarreglo contgiuo con producto máximo
Identificar el producto más alto posible entre todos los subarreglos contiguos no vacíos de numeros.

n = len(numeros)
min_prod = [0] * n
max_prod = [0] * n
min_prod[0] = max_prod[0] = numeros[0]
for i in range(1, n):
    candidatos = [
        numeros[i],
        max_prod[i - 1] * numeros[i],
        min_prod[i - 1] * numeros[i]
    ]
    max_prod[i] = max(candidatos)
    min_prod[i] = min(candidatos)
return max(max_prod)

(10) Partición equilibrada en dos subconjuntos
Verificar si un arreglo de enteros positivos numeros puede dividirse en dos subconjuntos cuyas sumas sean idénticas.

suma_total = sum(numeros)
if suma_total % 2 != 0:
    return False
objetivo = suma_total // 2
if max(numeros) > objetivo:
    return False

dp = [[False] * (objetivo + 1) for _ in range(len(numeros) + 1)]
dp[0][0] = True
for i in range(1, len(numeros) + 1):
    for j in range(objetivo + 1):
        dp[i][j] = dp[i - 1][j]
        if j >= numeros[i - 1]:
            dp[i][j] |= dp[i - 1][j - numeros[i - 1]]
return dp[len(numeros)][objetivo]

(11) Longitud de la secuencia de paréntesis válida más larga
Dada una cadena compuesta únicamente por '(' y ')', calcular la longitud del subsegmento válido más largo (todos los paréntesis están correctamente anidados y aparecen en pares consecutivos).

pila = [-1]
maxima_longitud = 0
for i, c in enumerate(s):
    if c == '(':
        pila.append(i)
    else:
        pila.pop()
        if not pila:
            pila.append(i)
        else:
            maxima_longitud = max(maxima_longitud, i - pila[-1])
return maxima_longitud