Cómo resolver problemas máximos de subarreglos de productos

Si la matriz tiene solo un elemento, devuelva ese elemento.
De lo contrario, calcule para cada índice los productos no positivos y no negativos de máxima magnitud de una subcadena contigua no vacía que termina allí. Devuelve el producto no negativo más grande encontrado.

Puede calcular los productos de magnitud máxima de la siguiente manera (usamos 0 como valor centinela):
Deje que [math] A_0, \ dots A_ {n-1} [/ math] denote los elementos de su matriz, luego
[matemáticas] p_0 = m_0 = 0, [/ matemáticas]

[matemáticas] p_ {i + 1} = \ left \ {\ begin {matrix} \ max (1, p_i) \ cdot A_i & \ text {if} A_i> 0 \\ m_i \ cdot A_i & \ text {de lo contrario} \ end {matriz} \ right., [/ math]

[matemáticas] m_ {i + 1} = \ left \ {\ begin {matrix} \ max (1, p_i) \ cdot A_i & \ text {if} A_i <0 \\ m_i \ cdot A_i & \ text {de lo contrario} \ end {matriz} \ derecha .. [/ matemáticas]

La respuesta es
[matemática] \ left \ {\ begin {matrix} A_0 & \ text {if} n = 1 \\\ max \ limits_ {i \ in [n]} p_i & \ text {de lo contrario} \ end {matrix} \ right .. [/mates]

Implementación:

int p=0,m=0,r=0;
if(n==1) r=A[0];
else for(int i=0;i p=max(1,p)*A[i], m*=A[i];
if(p<0) swap(p,m);
r=max(p,r);
}
(Esta solución funciona si las entradas de la matriz son números reales arbitrarios. Para el problema más específico donde todas las entradas son enteras, una solución alternativa sería dividir la matriz en valores 0 y devolver el producto de prefijo / sufijo máximo entre las submatrices resultantes. )

Utilicé un enfoque diferente y obtuve AC en GeeksForGeeks (no pude encontrar ningún otro OJ para probar la eficiencia y la corrección de mi código para este problema).

Algoritmo

1. Trataremos con diferentes subconjuntos separados por 0. Como dos o más subconjuntos con un cero entre ellos siempre dará un producto combinado como cero.
2. Mantendremos una variable que almacene el ‘producto obtenido hasta ahora’ después de encontrar el último cero. Es decir, una vez que encontramos un cero, comenzamos a tomar el producto del siguiente elemento con la inicialización de la variable manteniendo el ‘producto obtenido hasta ahora’ a 1. De este modo, podemos obtener el producto total de cada subcampo separado por cero.
3. Mantenemos otra variable que cuenta el número total de elementos negativos.
4. Se utiliza una variable más que almacena el producto hasta el “primer elemento negativo” en cada subcadena separada por cero (su uso se explicará más adelante).
5. Ahora, supongamos que estamos en un elemento con índice i, si el número total de elementos negativos hasta aquí es par entonces: ‘producto máximo que termina en i’ = producto hasta ahora.
   de lo contrario, si el número de elementos negativos es impar, entonces: ‘producto máximo que termina en i = producto máximo hasta ahora / producto hasta el primer elemento negativo.
   (eliminar el primer elemento negativo hará que el total de elementos negativos sea uniforme).
6. El máximo global se puede obtener tomando el máximo de ‘producto máximo para cada subcadena que termina en el índice i’.
7. El algoritmo se ejecuta en una complejidad de tiempo O (N).

Implementación de C ++:

#include
#definir isneg (x) ((x <0? 1: 0))
int ar [10];
int prodTillFirstNeg (int index, int elems, int & remove) {
eliminar = 1;
for (int i = index; i eliminar * = ar [i];
si (ar [i] <0)
volver i;
}
volver elems;
}
int getResl (int elems) {
int max_prod = 0, so_far = 1, current, negs = 0, remove, index = prodTillFirstNeg (0, elems, remove);
para (int i = 0; i if (ar [i] == 0) {
so_far = 1;
negs = 0;
index = prodTillFirstNeg (i + 1, elems, remove);
continuar;
}
negs + = isneg (ar [i]);
so_far * = ar [i];
if (negs% 2 == 0)
current = so_far;
más{
si (índice == i)
current = so_far / remove * ar [i];
más
current = so_far / remove;
}
max_prod = std :: max (max_prod, current);
}
return max_prod;
}
nulo resolver () {
int elems;
std :: cin >> elems;
para (int i = 0; i std :: cin >> ar [i];
std :: cout << getResl (elems) << std :: endl;
}
int main (int argc, char const * argv []) {
prueba int;
std :: cin >> prueba;
while (prueba–)
resolver();
devuelve 0;
}

Cuando la matriz solo tiene elementos positivos, el producto de todos los elementos será la respuesta.
El problema se vuelve interesante y complejo simultáneamente cuando hay elementos negativos.

La forma en que vi este problema es la siguiente.
Tiene tres opciones para hacer en cualquier posición de la matriz.
1. Puede obtener el producto máximo multiplicando el elemento actual con
Producto máximo calculado hasta ahora. (podría funcionar cuando actual
El elemento es positivo).
2. Puede obtener el producto máximo multiplicando el elemento actual con
producto mínimo calculado hasta ahora. (podría funcionar cuando actual
elemento es negativo).
3. El elemento actual podría ser una posición inicial para el subproducto máximo
formación

por lo que debe mantener el producto máximo actual y actual
producto mínimo

curr_max_prod = A [0];
prev_max_prod = A [0];
prev_min_prod = A [0];
ans = A [0];
para i = 1 a n-1
{
curr_max_prod = MAX (prev_max_prod * A [i],
prev_min_prod * A [i],
A [i]);

curr_min_prod = MIN (prev_max_prod * A [i],
prev_min_prod * A [i],
A [i]);
Ans = MAX (ans, curr_max_prod);
prev_max_prod = curr_max_prod;
prev_min_prod = curr_min_prod;
}
volver ans;

El algoritmo anterior requiere O (n) tiempo y espacio constante, muy similar al algoritmo de Kadane.

La siguiente función devuelve la submatriz máxima de productos:

static int getMaximumProductSubarray (int [] arr)
{
int currentPositive = arr [0];
int currentNegative = arr [0];
int globalPositivo = arr [0];
int globalNegative = arr [0];
para (int i = 1; i {
int temp = currentPositive;
currentPositive = Math.max (arr [i], Math.max (currentPositive * arr [i], currentNegative * arr [i]));
currentNegative = Math.min (arr [i], Math.min (temp * arr [i], currentNegative * arr [i]));
OverallPositive = Math.max (OverallPositive, currentPositive);
OverallNegative = Math.min (OverallNegative, currentNegative);
}
return global Positivo;
}

Extienda la lógica utilizada en el algoritmo de Kadane, que es

maxCurrentSum = maxGlobalSum = A [0];
para (int i = 1; i maxCurrentSum = max ({A [i], maxCurrentSum + A [i]});
maxGlobalSum = max (maxGlobalSum, maxCurrentSum);
}
return maxGlobalSum;

Considere la matriz {2, 4, 6, -9, 8, -1}. Observe que cuando i = 3, la continuidad del producto más grande se rompe porque A [i] = -9 y el producto contiguo se volverá negativo. Aquí, podemos continuar con el algoritmo y terminaremos con el producto contiguo Max = 48, que es incorrecto.

Sin embargo, si multiplicaste -9 x 48, entonces en i = 5, obtendrás un producto más alto debido a que tenías un producto mínimo cuando multiplicado por -1 (o cualquier número negativo) dio un producto más alto que su actual.

Así que esencialmente rastreamos los productos actuales más altos y más bajos y seguimos eligiendo el máximo entre estos dos.

int maxProduct (const vector & A) {
int n = A.size ();
if (n == 0) devuelve -1;
int maxGlobal = A [0], maxCurrent = A [0], minCurrent = A [0];
para (int i = 1; i int savedMaxCurrent = maxCurrent;
maxCurrent = max ({A [i], salvadoMaxCurrent * A [i], minCurrent * A [i]});
minCurrent = min ({A [i], salvadoMaxCurrent * A [i], minCurrent * A [i]});
maxGlobal = max ({maxGlobal, maxCurrent, minCurrent});
// cout << "MxC:" << maxCurrent << ", MnC:" << minCurrent << ", MxG:" << maxGlobal << "\ n";
}
return maxGlobal;
}

¿Qué hay de esta solución?
Pasos de algoritmo

1. Calcule el producto tan lejos del lado izquierdo y manténgalo en el producto máximo.
2.cuando obtienes cero en la actualización del producto con 1.

2.Después de eso, calcule el producto desde el lado derecho y actualice el máximo cuando el producto sea mayor que el máximo.
mi algo atraviesa dos veces toda la matriz.
ejemplo
-1, -2, -3,0,4
1.calcular desde el lado izquierdo:
ans será 4
2.calcular desde el lado derecho:
ans se actualizará con 6.
así que la respuesta final es 6
dime si estoy equivocado