Como no se menciona en la pregunta, explicaré un algoritmo para una pregunta similar.
Encuentre la longitud máxima de una sub-matriz creciente en la matriz.
El algoritmo para esto es bastante simple y se ejecuta en tiempo O (n).
- ¿Por qué se han desarrollado los algoritmos de ordenamiento O (n ^ 2) (como el ordenamiento por inserción y el ordenamiento por burbuja) y para qué se utilizan?
- ¿Existe un método o algoritmo matemático para expresar la suma de un número y un número multiplicado por un radical como la fórmula (a + b) ^ 3?
- ¿Qué estructura de datos debo usar en Java para almacenar y obtener el siguiente tipo de datos? ¿Cuál debería ser la estructura de mi clase para este propósito?
- ¿Cuál es la estrategia de divide y vencerás? Escribe un algoritmo para encontrar x a la enésima potencia usando el método de dividir y conquistar.
- Cómo validar un algoritmo de stock
Necesita dos variables, max_len y cur_len. max_len es la longitud máxima de una sub-matriz creciente, mientras que cur_len es la longitud de la sub-matriz actual que se analiza.
- Inicialice max_len a 1 y cur_len a 1. max_len 0 por razones obvias. cur_len 1 porque, cuando comienzas a analizar alguna sub-matriz, en el primer elemento la longitud de esta sub-matriz en particular es siempre 1.
- Suponga que está en el índice i de la matriz arr, (elemento arr [i]). Si arr [i]> arr [i-1], incremente cur_len. Porque si esto es así, entonces este elemento es parte de la sub-matriz creciente en el análisis y, por lo tanto, cur_len debería incrementarse. Compare este valor con max_len, si cur_len> max_len, actualice max_len al valor de cur_len, porque acaba de encontrar una matriz secundaria más grande que la matriz secundaria encontrada anteriormente.
- Si arr [i] <arr [i-1], ha llegado al final de su subarray creciente y es hora de restablecer cur_len. Establezca cur_len nuevamente en 1. (Explicación provista en el primer punto)
- Después de que se complete la iteración, tendrás tu respuesta.
Ejemplo, para la matriz 11, 12, 13, 14, 15, 5, 6, 7, 8, 9, 10, -4, -3, -2, -1, su respuesta debe ser 6. La sub-matriz 5, 6, 7, 8, 9, 10 está aumentando y tiene 6 elementos. Cuál es el más grande de todos los otros sub-arrays.
Implementación en C ++ del algoritmo.
#include
usando el espacio de nombres estándar;
int main ()
{
int i, arr [100], max_len, cur_len, n;
cin >> n;
para (i = 0; i <n; i ++)
{
cin >> arr [i];
}
max_len = 1; // Punto de viñeta 1
cur_len = 1;
para (i = 1; i <n; i ++)
{
if (arr [i]> arr [i-1]) // Punto 2
{
cur_len ++;
max_len = max_len <cur_len? cur_len: max_len;
}
más // Punto de viñeta 3
{
cur_len = 1;
}
}
cout << max_len << endl;
devuelve 0;
}
Siéntase libre de comentar si hay algún problema.
