Encuentra la secuencia contigua con el producto más grande de una matriz de enteros

Question

he llegado con el código de abajo, pero que no satisface todos los casos, por ejemplo:

1. matriz que tiene todo de 0

2. array con valores negativos (que es poco complicado ya que se trata de encontrar el producto como dos enteros negativos dar valor positivo)

   public static int LargestProduct(int[] arr) 
   { 
       //returning arr[0] if it has only one element 
       if (arr.Length == 1) return arr[0]; 
   
       int product = 1; 
       int maxProduct = Int32.MinValue; 
   
       for (int i = 0; i < arr.Length; i++) 
       { 
        //this block store the largest product so far when it finds 0 
        if (arr[i] == 0) 
        { 
         if (maxProduct < product) 
         { 
          maxProduct = product; 
         } 
         product = 1; 
        } 
        else 
        { 
         product *= arr[i]; 
        } 
       } 
       if (maxProduct > product) 
        return maxProduct; 
       else 
        return product; 
   } 
   

¿Cómo puedo incorporar los casos anteriores/corregir el código? Por favor recomiende.

Answer 1

Su problema básico es 2 partes. Romperlos y resolverlos se vuelve más fácil.

1) Buscar todos los subconjuntos contiguos.

Dado que su secuencia de origen puede tener valores negativos, no está tan equipado para hacer juicios de valor hasta que encuentre cada subconjunto, ya que un negativo puede ser "cancelado" por otro. Entonces, deje que la primera fase sea encontrar solo los subconjuntos.

Un ejemplo de cómo se puede hacer esto es el siguiente código

// will contain all contiguous subsets 
var sequences = new List<Tuple<bool, List<int>>>(); 

// build subsets 
foreach (int item in source) 
{ 
    var deadCopies = new List<Tuple<bool, List<int>>>(); 

    foreach (var record in sequences.Where(r => r.Item1 && !r.Item2.Contains(0))) 
    { 
     // make a copy that is "dead" 
     var deadCopy = new Tuple<bool, List<int>>(false, record.Item2.ToList()); 
     deadCopies.Add(deadCopy); 

     record.Item2.Add(item); 
    } 

    sequences.Add(new Tuple<bool, List<int>>(true, new List<int> { item })); 
    sequences.AddRange(deadCopies); 
} 

En el código anterior, estoy construyendo todos mis subconjuntos contiguos, teniendo la libertad de no añadir nada a un subconjunto dado que ya tiene un valor de 0 Puede omitir ese comportamiento en particular si lo desea.

2) Calcule el producto de cada subconjunto y compárelo con un valor máximo.

Una vez que haya encontrado todos sus subconjuntos elegibles, la siguiente parte es fácil.

// find subset with highest product 
int maxProduct = int.MinValue; 
IEnumerable<int> maxSequence = Enumerable.Empty<int>(); 

foreach (var record in sequences) 
{ 
    int product = record.Item2.Aggregate((a, b) => a * b); 
    if (product > maxProduct) 
    { 
     maxProduct = product; 
     maxSequence = record.Item2; 
    } 
} 

Agregue cualquier lógica que desee restringir la longitud de la fuente original o los candidatos del subconjunto o los valores del producto. Por ejemplo, si desea imponer requisitos de longitud mínima en cualquiera de ellos, o si se permite un producto subconjunto de 0 si está disponible un producto distinto de cero.

Además, no hago ninguna afirmación sobre el rendimiento del código, es simplemente para ilustrar la división del problema en sus partes.

Answer 2

Creo que deberías tener 2 productos al mismo tiempo, serán diferentes en los signos. Sobre caso, cuando todos los valores son cero - se puede comprobar al final si sigue siendo maxProduct Int32.MinValue (si Int32.MinValue no es realmente posible) Mi variante:

int maxProduct = Int32.MinValue; 
int? productWithPositiveStart = null; 
int? productWithNegativeStart = null; 

for (int i = 0; i < arr.Length; i++) 
    { 
     if (arr[i] == 0) 
     { 
      productWithPositiveStart = null; 
      productWithNegativeStart = null; 
     } 
     else 
     { 
      if (arr[i] > 0 && productWithPositiveStart == null) 
      { 
       productWithPositiveStart = arr[i];    
      } 
      else if (productWithPositiveStart != null) 
      { 
       productWithPositiveStart *= arr[i]; 
       maxProduct = Math.max(maxProduct, productWithPositiveStart); 
      } 
      if (arr[i] < 0 && productWithNegativeStart == null) 
      { 
       productWithNegativeStart = arr[i]; 
      } 
      else if (productWithNegativeStart != null) 
      { 
       productWithNegativeStart *= arr[i]; 
       maxProduct = Math.max(maxProduct, productWithNegativeStart); 
      } 
      maxProduct = Math.max(arr[i], maxProduct); 
     }    
    } 
if (maxProduct == Int32.MinValue) 
{ 
    maxProduct = 0; 
} 

Answer 3

A un alto nivel, su el algoritmo actual divide la matriz en un 0 y devuelve el producto contiguo más grande de estas sub-matrices. Cualquier iteración adicional será en el proceso de encontrar el producto contiguo más grande de una matriz secundaria donde no hay elementos 0.

Para tener en cuenta los números negativos, obviamente, primero tenemos que probar si el producto de uno de estos sub -arrays es negativo, y toma alguna acción especial si lo es.

El resultado negativo proviene de un número impar de valores negativos, por lo que debemos eliminar uno de estos valores negativos para que el resultado sea positivo nuevamente. Para hacer esto eliminamos todos los elementos hasta el primer número negativo, o el último número negativo y todos los elementos después de eso, lo que resulte en el producto más alto.

Para tener en cuenta una matriz de todos los 0, simplemente use 0 como su producto máximo inicial. Si la matriz tiene un único valor negativo, significa que el manejo especial de un solo elemento significará que se devuelve. Después de eso, siempre habrá un producto de subsecuencia positiva, o toda la matriz es 0 y debería devolver 0 de todos modos.

Answer 4

Estoy basando mi respuesta en el supuesto de que si tiene más de 1 elemento en la matriz, querrá multiplicar al menos 2 enteros contiguos para verificar la salida, es decir, en una matriz de {-1, 15}, el resultado que desea es -15 y no 15).

El problema que tenemos que resolver es mirar todas las combinaciones de multiplicación posibles y descubrir el producto máximo de ellas.

El número total de productos en una matriz de n enteros sería nC2, es decir, si hay 2 elementos, entonces las combinaciones de multiplicación total serían 1, para 3, sería 3, para 4, sería 6 y pronto.

Para cada número que tenemos en la matriz entrante, tiene que multiplicarse con todas las multiplicaciones que hicimos con el último elemento y mantener el producto máximo hasta ahora y si lo hacemos para todos los elementos, al final nos quedaríamos con el producto máximo.

Esto debería funcionar para negativos y ceros.

public static long LargestProduct(int[] arr) 
    { 
     if (arr.Length == 1) 
      return arr[0]; 

     int lastNumber = 1; 
     List<long> latestProducts = new List<long>(); 
     long maxProduct = Int64.MinValue; 
     for (int i = 0; i < arr.Length; i++) 
     { 
      var item = arr[i]; 
      var latest = lastNumber * item; 
      var temp = new long[latestProducts.Count]; 
      latestProducts.CopyTo(temp); 
      latestProducts.Clear(); 
      foreach (var p in temp) 
      { 
       var product = p * item; 
       if (product > maxProduct) 
        maxProduct = product; 
       latestProducts.Add(product); 
      } 
      if (i != 0) 
      { 
       if (latest > maxProduct) 
        maxProduct = latest; 
       latestProducts.Add(latest); 
      } 
      lastNumber = item; 
     } 
     return maxProduct; 
    } 

Si desea que el producto máximo de incorporar también el único elemento presente en la matriz es decir {-1, 15} debe escrito 15, a continuación, se puede comparar el producto max con el elemento de la matriz que se está procesando y eso debería darle el producto máximo si el elemento individual es el número máximo. Esto se puede lograr agregando el siguiente código dentro del bucle for al final.

if (item > maxProduct) 
    maxProduct = item; 

Answer 5

se puede hacer en O(N). se basa en la idea simple: calcule el mínimo (minCurrent) y el máximo (maxCurrent) hasta el i. Esto se puede cambiar fácilmente para adaptarse a la enfermedad como: {0,0,-2,0} or {-2,-3, -8} or {0,0}

a[] = {6, -3, 2, 0, 3, -2, -4, -2, 4, 5}

steps of the algorithm given below for the above array a :

private static int getMaxProduct(int[] a) { 
    if (a.length == 0) { 
     throw new IllegalArgumentException(); 
    } 
    int minCurrent = 1, maxCurrent = 1, max = Integer.MIN_VALUE; 
    for (int current : a) { 
     if (current > 0) { 
      maxCurrent = maxCurrent * current; 
      minCurrent = Math.min(minCurrent * current, 1); 
     } else if (current == 0) { 
      maxCurrent = 1; 
      minCurrent = 1; 
     } else { 
      int x = maxCurrent; 
      maxCurrent = Math.max(minCurrent * current, 1); 
      minCurrent = x * current; 
     } 
     if (max < maxCurrent) { 
      max = maxCurrent; 
     } 
    } 
    //System.out.println(minCurrent); 
    return max; 
}