algorithm - tecnicas - El producto máximo de elementos consecutivos en una matriz.

metodologia design thinking

Question

Me hicieron esta pregunta de algoritmo durante mi entrevista en el sitio. Como no me pidieron que firmara la NDA, la publico aquí para obtener una respuesta.

Dado un conjunto de números REALES que no contienen 0, encuentre los elementos consecutivos que producen el producto máximo. El algoritmo debe ejecutarse en tiempo lineal.

He considerado el siguiente enfoque: Utilice dos matrices. La primera es usar la idea de DP para registrar el producto de valor absoluto máximo actual, la segunda matriz para registrar el número de elementos negativos encontrados hasta el momento. El resultado final debe ser el mayor valor absoluto máximo y el número de números negativos sea par.

Pensé que mi método funcionaría, pero fue interrumpido durante la codificación diciendo que no funcionará. Por favor, hágamelo saber lo que falta en el enfoque anterior.

Answer 1

Cuidar la cosa si no hay 1 en la matriz y el producto que viene no debería ser 1 en ese caso. Aquí está mi código:

#include<bits/stdc++.h>
using namespace std;

int max(int x, int y)
{ return (y > x)? y : x; }
int min(int x, int y)
{ return (y < x)? y : x; }
bool search(int a[],int k,int n)
{
    for(int i=0;i<n;i++)
    {
        if(a[i]==k)
        return true;
    }
    return false;
}

int maxSubArrayProduct(int a[], int size)
{
   int maxpos = 1, minneg=1, i;
   int pro_max = 1;

   for (i = 0; i < size; i++)
   {
        if(a[i]<0)
        {
            int temp=maxpos;
            maxpos=max(maxpos,minneg*a[i]);
            minneg=min(minneg,temp*a[i]);
        }
        if(a[i]==0)
        {maxpos=1;minneg=1;}
        if(a[i]>0)
        {
            maxpos=maxpos*a[i];
            minneg=min(minneg,minneg*a[i]);
        }
        if(pro_max<maxpos)
        pro_max=maxpos;
   }
   return pro_max;
}

/* Driver program to test maxSubArrayProduct */
int main()
{
   int a[] =  {-1,0,1};
   int n = sizeof(a)/sizeof(a[0]);
   int start=0,end=0;
   int max_pro = maxSubArrayProduct(a, n);
   if(max_pro==1)
   if(search(a,1,n))max_pro=1;
   else max_pro=0;
   printf("Maximum contiguous product is %d/n", max_pro);
   return 0;
}

Answer 2

El algoritmo es de hecho O (n). Al iterar la matriz, use una variable para almacenar el valor máximo encontrado hasta ahora, una variable para almacenar el valor máximo de la subarray que termina en [i] y otra variable para almacenar el valor mínimo que termina en [i] valores negativos.

float find_maximum(float arr[], int n) {
    if (n <= 0) return NAN;

    float max_at = arr[0];  // Maximum value that ends at arr[i]
    float min_at = arr[0];  // Minimum value that ends at arr[i]
    float max_value = max_at;

    for (int i = 1; i < n; i++) {
        float prev_max_at = max_at, prev_min_at = min_at;
        max_at = max(arr[i], arr[i] * prev_min_at, arr[i] * prev_max_at);
        min_at = min(arr[i], arr[i] * prev_min_at, arr[i] * prev_max_at);
        max_value = max(max_value, max_at);
    }
    return max_value;
}

Answer 3

En el resultado O (n). Encuentre los elementos consecutivos que producen el producto máximo, multiplicando cada elemento de izquierda a derecha y guardándolos en una lista. Si el nuevo producto es más grande que el último, multiplique el siguiente elemento y actualice la lista. Si no es así empieza una nueva lista y repite. Algoritmo en Python 3.3:

import numpy as np

x = [-500,-400,200,0.1,-100,20,-10,2]

prod_seq_lists = [[x[0], x[1]]]  # Start assuming the first 2 elements have max product and save them in a list
product_result = []  # Contains the product of each list


for e in x[2:]:  # Start for loop from 3rd element
    if x[0] == 0 or x[1] == 0 or e == 0:  # Raise error if there''s a 0
        raise IndexError(''Found 0'')

    temp_b = np.prod(prod_seq_lists[-1])  # Calculate the product of the last list in max_prod_seq
    temp_a = temp_b * e  # Multiply the new_element

    if temp_a >= temp_b:  # If last_list*new_element >= last_list
        prod_seq_lists[-1].append(e)  # Append the new_element in your last_list

        if e == x[-1]:
            product_result.append(temp_a)  # Save the product of the last list

    else:
        product_result.append(temp_b)  # Save the product of each list
        prod_seq_lists.append([e])  # Else, append append the new element in a new_list


print("Your array: ", prod_seq_lists)
print("The list with max product of consecutive elements: ", prod_seq_lists[np.argmax(product_result)])  # Get index of the maximum product and print that list
print("The max product of consecutive elements: ", max(product_result))

Devoluciones :

Your array:  [[-50, -40, 20], [0.1], [-100], [20], [-10], [90, 1000]]
The list with max product of consecutive elements:  [90, 1000]
The max product of consecutive elements:  90000

Answer 4

Escribí el código a continuación, para encontrar el producto máximo de valores enteros adyacentes en la matriz de entrada, asumiendo que el producto también estaría en el rango int, iteraría el bucle solo 2 veces

int adjacentElementsProduct(int[] inputArray) {

    int maxProdct=inputArray[0]*inputArray[1];
//as we have already taken product of first two , start from 3rd and iterate till second last because we are checking the product of i+1 for every i
    for (int i=2; i<inputArray.length-1; i=i+2){
        if(inputArray[i-1]*inputArray[i] >inputArray[i]*inputArray[i+1]){
            if(inputArray[i-1]*inputArray[i]>maxProdct)
                maxProdct =inputArray[i-1]*inputArray[i];
        }
        else if(inputArray[i+1]*inputArray[i] > maxProdct)
            maxProdct=inputArray[i+1]*inputArray[i];



    }
//if its an even array the last element would have been covered while calculating product with second last, otherwise we would check the product for last and second last element and compare with maxProduct
    if(inputArray.length%2 !=0){
        if(maxProdct<inputArray[inputArray.length-1]*inputArray[inputArray.length-2]){
            maxProdct=inputArray[inputArray.length-1]*inputArray[inputArray.length-2];
        }
    }
    return maxProdct;

}

Answer 5

Ignorando números negativos por el momento ...

Deje que A[i..j] signifique A[i]*A[i+1]*...*A[j]

El problema es encontrar max(A[i..j])

Observe que A[i..j] = A[0..j] / A[0..i-1]

Entonces si calculamos A[0..x] para todo x.

Entonces podemos determinar max(A[i..j]) = max(A[0..x]) / min(A[0..y])

Answer 6

Puede implementar una variante del algoritmo de Kadane ( http://en.wikipedia.org/wiki/Maximum_subarray_problem ) que se ejecuta con memoria extra constante y lineal en el tamaño del problema (sin matriz adicional, ...)

Si solo se dan números positivos estrictos:

def max_subarray_mul(A):
    max_ending_here = max_so_far = 1
    for x in A:
        if x > 0
            max_ending_here = max(1,max_ending_here*x)
            max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

Sigo trabajando en la parte con números negativos.

O un método más caro (en tiempo) es el siguiente, pero esto funcionará con números negativos:

def max_subarray_mul(A):
    max_so_far = 1
    n = length(A)
    for i in 1...n:
        x = A[i]
        tmp = x
        max_so_far = max(max_so_far,tmp)
        for j in i+1...n:
          tmp = tmp*A[j]
          max_so_far = max(max_so_far,tmp)
    return max_so_far

Que se ejecuta en memoria constante y tiempo O(n²)

Answer 7

Usando notaciones python:

• calcular min( prod( v[ 0: ] ), prod( v[ 1: ] ), ..., prod( v[ -1 ] ) ) y max( prod( v[ 0: ] ), prod( v[ 1: ] ), ..., prod( v[ -1 ] ) ) en O (n)
• calcule recursivamente el producto máximo basándose en el hecho de que maxpro(v) = max( maxpro(v[:-1]) * max( prod( v[ 0: ] ), prod( v[ 1: ] ), ..., prod( v[ -1 ] ) ) . Esto también es O (n)

Aquí está el código:

#
n = 5
vmax = 10

#
v = nr.randint( 1, vmax, n )
v *= nr.randint( 0, 2, n ) * 2 - 1
#
print v

#
prod_res = np.zeros( ( 2, n ), int )
prod_res[ 0, 0 ] = prod_res[ 1, 0 ] = v[ 0 ]
for i in xrange( 1, n ) :
    prod_res[ 0, i ] = min( v[ i ], prod_res[ 1, i-1 ] * v[ i ], prod_res[ 0, i-1 ] * v[ i ] )
    prod_res[ 1, i ] = max( v[ i ], prod_res[ 1, i-1 ] * v[ i ], prod_res[ 0, i-1 ] * v[ i ] )
#
print prod_res

#
def maxpro_naive( v ) :
    return v[ 0 ] if ( len( v ) == 1 ) else max( maxpro_naive( v[ :-1 ] ), prod_res[ 1, len(v) -1 ] )
#
print maxpro_naive( v )