Dada la siguiente pregunta no decreciente,Encuentra más larga secuencia
Dada una matriz de enteros A de longitud n, encontrar la secuencia más larga {i_1, ..., i_k} tal que i_j < i_ (j + 1) y A [i_j] < = A [i_ (j + 1)] para cualquier j en [1, k-1].
Aquí está mi solución, ¿es esto correcto?
max_start = 0; // store the final result
max_end = 0;
try_start = 0; // store the initial result
try_end = 0;
FOR i=0; i<(A.length-1); i++ DO
if A[i] <= A[i+1]
try_end = i+1; // satisfy the condition so move the ending point
else // now the condition is broken
if (try_end - try_start) > (max_end - max_start) // keep it if it is the maximum
max_end = try_end;
max_start = try_start;
endif
try_start = i+1; // reset the search
try_end = i+1;
endif
ENDFOR
// Checking the boundary conditions based on comments by Jason
if (try_end - try_start) > (max_end - max_start)
max_end = try_end;
max_start = try_start;
endif
De alguna manera, no creo que esta es una solución correcta, pero no puedo encontrar un contraejemplo que desaprueba esta solución.
¿alguien puede ayudar?
Gracias
Me parece bastante bueno. ¿Puedes darme una idea de por qué crees que es incorrecto? –