Data la seguente domanda,Trova più lunga sequenza non decrescente
dato un array di interi A di lunghezza n, trovare la sequenza più lunga {I_1, ..., i_k} tale che i_j < i_ (j + 1) e A [i_j] < = A [i_ (j + 1)] per qualsiasi j in [1, k-1].
Ecco la mia soluzione, è corretta?
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
In qualche modo, non credo che questa è una soluzione corretta, ma non riesco a trovare un contro-esempio che disapprovano questa soluzione.
chiunque può aiutare?
Grazie
Mi sembra abbastanza buono. Puoi dare qualche idea del perché pensi che sia scorretto? –