Dado un vector comoprograma eficiente para imprimir/retorno todos subsecuencias crecientes de tamaño 3 en una matriz
1, 6, 5, 2, 3, 4
que necesita imprimir
1 2 3
1 3 4
1 2 4
2 3 4
¿Cuál es la mejor manera de hacer esto? ¿Es esta programación dinámica?
¿Hay una mejor manera de hacer que la bruteforce O (n3)? Estoy seguro de que hay
La razón por la que dicen programación dinámica es porque puedo ver esto como algo así como
para '1' (imprimir todos los resultados de sub problema del resto de la matriz con subsecuencias de tamaño 2).
de '2' (imprimir todos los resultados de los problemas sub del resto de la matriz con subseqences de tamaño 2)
y seguir así.
Sin embargo, hay una gran cantidad de superposición en los dos resultados anteriores, por lo que tenemos que encontrar una forma eficiente de reutilizar eso, supongo.
Bueno, estos son solo pensamientos aleatorios. Puedes corregirme con el appraoch correcto.
Bien, déjenme corregir, si no se imprime, necesito las diferentes secuencias de incremento devueltas. Mi punto es que necesito encontrar un enfoque para llegar a estas secuencias de la manera más eficiente.
¿qué idioma? o es un lenguaje agnóstico? ¿Cuál es el tamaño máximo de la matriz de entrada? – Kiril
bien agnóstico del lenguaje. Necesito un enfoque. Puedes pensar en el tamaño de la matriz de entrada entre 10 y un millón :) – AMM
Si necesitas imprimir cada subsecuencia, no hay nada mejor que 'O (n^3)'. Si solo quieres contarlos sin embargo, entonces puedes hacerlo mejor. – IVlad