Diseña un algoritmo usando la técnica de programación dinámica para resolver el siguiente problema: Sea N un entero positivo y sean A y B dos arreglos A[1], A[2], ..., A[N] y B[1], B[2], ..., B[N] de enteros positivos. Los índices 1 <= I1 < I2 < ... < IK <= N y 1 <= J1 < J2 < ... < JK <= N forman un subarreglo ascendente común de A y B de longitud K si se cumple que A[I1] = B[J1] < A[I2] = B[J2] < ... < A[IK] = B[JK]. Su algoritmo deberá encontrar un subarreglo ascendente común de A y B con la mayor longitud posible. Por ejemplo, si N = 9, A = [3, 1, 4, 1, 5, 9, 2, 6, 5] y B = [9, 2, 1, 3, 4, 6, 5, 7, 6] entonces los índices I1 = 1, I2 = 3, I3 = 5 e I4 = 8 y J1 = 4, J2 = 5, J3 = 7 e I4 = 9 forman el subarreglo ascendente [3, 4, 5, 6] de longitud 4. Escribe un programa llamado sascomZZ (donde ZZ es la clave de dos dígitos asignada por el profesor) basado en tu algoritmo que acepte como entrada el entero positivo N y dos arreglos A y B de N enteros positivos y que escriba como salida la máxima longitud K de un subarreglo ascendente común de A y B. Puedes suponer que 1 <= N <= 1000 y que A y B son arreglos de int.
| Ejemplo de entrada |
Ejemplo de salida |
| 9 3 1 4 1 5 9 2 6 5 9 2 1 3 4 6 5 7 6 |
4 |