Estoy proporcionando esta solución. No estoy seguro de si es correcto, pero funcionó para mí y es correcto hasta que demuestre que está equivocado. 😛
Haré dos matrices.
Derecha = la i-ésima entrada de esta matriz contiene el elemento más grande en el lado derecho del elemento actual.
Izquierda = la entrada i-ésima de esta matriz contendrá el elemento más grande en el lado izquierdo del elemento actual que es más pequeño que el número i.
Calcular la matriz correcta es fácil. Comenzaremos desde la última posición. Mantendremos una variable máxima y si el elemento actual es máximo, estableceremos la derecha [i] como -1; de lo contrario, estableceremos la derecha [i] en el último máximo.
Por ejemplo: para matriz: 6 9 12 17 11 15
Derecha: 17 17 17 -1 15 -1
Calcular la matriz de la izquierda es un poco engorroso. Modificaremos un poco la definición de la matriz de la izquierda , es decir, si pensamos que el elemento actual no puede ser parte de la secuencia, pondremos Left [current] = -1 . Debido a que no hay beneficio de calcular el elemento más grande en su lado izquierdo, que es más pequeño que el elemento actual. Además, veremos que si la Derecha [actual] es -1, entonces tampoco hay beneficio de calcular Izquierda [actual] , porque este elemento actual no puede ser parte de la secuencia. (Porque cuando calculamos la secuencia, este no puede ser el elemento del medio). Entonces, usaremos una Pila. Veremos si hay algún elemento en la pila, si hay alguno, intentaremos encontrar el elemento máximo de la pila que sea menor que el elemento actual, si se encuentra algún número mayor que el elemento actual, entonces nos detendremos y empuje el elemento i de la matriz. Pero, ¿cómo se asegura de que funcionará?
Digamos, tenemos n números y los primeros 4 números son a, b, c, d donde a <b <c, pero d a . Puede haber un caso en el que a, d y x (x viene después, estos 4 números x> c & x> d) forman el triplete, pero este no puede ser el máximo porque a. c y x formarán un triplete cuyo producto es más que el producto de a, b, c.
- ¿Hay alguna manera de extraer la palabra principal de una lista de sinónimos que representa la lista?
- ¿Es posible tener un número de elementos en una matriz más que el tamaño de la matriz que se define en un momento de compilación?
- ¿Cómo se puede ser bueno para resolver problemas de algoritmos / programación? Soy un principiante, y me sugirieron que leyera el libro CLRS para aprender sobre algoritmos.
- ¿Cómo demostramos que el algoritmo de codificación de Huffman es óptimo?
- ¿Es posible codificar un programa que, dada una secuencia finita, encuentra al menos 2 reglas posibles que generan las series restantes?
Por ejemplo :
En 6,9,12,17,11,15.
cuando se encuentra 11, la pila contendrá el elemento 12, pero no encontraremos ningún elemento menor que 11 en el lado izquierdo, porque no hay ningún beneficio al hacerlo, porque de todos modos 11 no puede ser parte del triplete (O 12 es el primer elemento del triplete o el segundo, por lo que 11 no puede participar en la formación de este triplete). Simplemente pondremos left [4] = -1.
Sé que es un poco tedioso, pero debería funcionar. Aquí está el código, ejecútelo en múltiples casos de prueba y si encuentra algo incorrecto, notifíqueme. Gracias A2A Lehar Bhandari.
#include
#include
#include
#include
usando el espacio de nombres estándar;
#define s (n) scanf (“% d”, & n)
int main ()
{
int n;
s (n);
int * arr = nuevo int [n];
para (int i = 0; i <n; i ++) s (arr [i]);
int * left = new int [n];
int * right = new int [n];
para (int i = 0; i <n; i ++)
{
izquierda [i] = 0;
derecha [i] = 0;
}
// Calculando la matriz correcta
int max = INT_MIN;
para (int i = n-1; i> = 0; i–)
{
si (max <arr [i])
{
max = arr [i];
derecha [i] = -1;
}
más a la derecha [i] = max;
}
/ * para (int i = 0; i <n; i ++)
{
printf (“% d”, derecha [i]);
}
printf (“\ n”); * /
// Calculando la matriz izquierda.
apilar s;
para (int i = 0; i <n; i ++)
{
si (derecha [i] == -1)
{
izquierda [i] = -1;
continuar;
}
max = -1;
while (! s.empty () && s.top () <arr [i])
{
max = s.top ();
s.pop ();
}
izquierda [i] = max;
s.push (arr [i]);
}
/ * para (int i = 0; i <n; i ++)
{
printf (“% d”, izquierda [i]);
}
printf (“\ n”); * /
max = INT_MIN;
int ni = 0;
int nj = 0;
int nk = 0;
para (int i = 1; i <n-1; i ++)
{
if (max <izquierda [i] * arr [i] * derecha [i])
{
ni = izquierda [i];
nj = arr [i];
nk = derecho [i];
max = izquierda [i] * arr [i] * derecha [i];
}
}
printf (“% d \ n”, max);
printf (“% d% d% d \ n”, ni, nj, nk);
devuelve 0;
}
