Después de eliminar ~K~ dígitos del número de ~N~ dígitos, permanecerán ~N-K~ dígitos. Entonces podemos reformular el enunciado del problema y decir que debemos elija ~N-K~ dígitos que formen el número máximo posible.

Usaremos un enfoque greedy. Encontramos el dígito más grande que aún permite agregar dígitos adicionales después de él, y colocarlo como el primer dígito de nuestro solución. Repetimos esto para el segundo dígito y así sucesivamente. Si hay múltiples opciones en cualquier momento, es fácil ver que podemos elegir el el más a la izquierda sin dañar nuestra mejor solución.

Si no elegimos el dígito más grande posible en algún momento, obviamente terminan con un número más pequeño, lo que significa que nuestro el algoritmo es correcto.

Habilidades necesarias: análisis de problemas matemáticos

Categoría: algoritmos greedy