Подтвердить что ты не робот

Максимальное произведение последовательных элементов в массиве

Мне был задан этот вопрос с алгоритмом во время моего интервью на месте. Поскольку меня не просили подписать NDA, я отправляю его здесь для получения ответа.

Учитывая массив чисел REAL, который не содержит 0, найдите последовательные элементы, которые дают максимальный продукт. Алгоритм должен выполняться в линейном времени

Я рассмотрел следующий подход: Используйте два массива. Во-первых, использовать идею DP для записи текущего максимального абсолютного значения продукта, а второй - для записи количества отрицательных элементов, встречающихся до сих пор. Конечным результатом будет максимальное максимальное абсолютное значение, а число отрицательных чисел будет четным.

Я думал, что мой метод будет работать, но был прерван во время кодирования, говоря, что это не сработает. Пожалуйста, дайте мне знать, чего не хватает в вышеуказанном подходе.

4b9b3361

ОТВЕТЫ

Ответ 1

Алгоритм действительно O (n). При повторении массива используйте переменную для хранения значения max, найденного до сих пор, переменной для хранения максимального значения подмассива, которое заканчивается на [i], и другой переменной для сохранения минимального значения, которое заканчивается на [i] для лечения отрицательные значения.

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;
}

Ответ 2

Вы можете реализовать вариант алгоритма Кадане (http://en.wikipedia.org/wiki/Maximum_subarray_problem), который работает с постоянной дополнительной памятью и линейным по размеру проблемы (нет дополнительного массива,...)

Если заданы только строгие положительные числа:

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

Я все еще работаю над частью с отрицательными цифрами

Или более дорогим (по времени) методом является следующее, но это будет работать с отрицательными номерами:

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

который работает в постоянной памяти и O(n²) время

Ответ 3

Использование питонных обозначений:

  • вычислить min( prod( v[ 0: ] ), prod( v[ 1: ] ), ..., prod( v[ -1 ] ) ) и max( prod( v[ 0: ] ), prod( v[ 1: ] ), ..., prod( v[ -1 ] ) ) в O (n)
  • вычислить рекурсивно максимальный продукт на основании того, что maxpro(v) = max( maxpro(v[:-1]) * max( prod( v[ 0: ] ), prod( v[ 1: ] ), ..., prod( v[ -1 ] ) ). Это тоже O (n)

Вот код:

#
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 )

Ответ 4

Игнорирование отрицательных чисел на данный момент...

Пусть A[i..j] означает A[i]*A[i+1]*...*A[j]

Задача состоит в том, чтобы найти max(A[i..j])

Обратите внимание, что A[i..j] = A[0..j] / A[0..i-1]

Итак, если мы вычислим A[0..x] для всех x.

Затем мы можем определить max(A[i..j]) = max(A[0..x]) / min(A[0..y])

Ответ 5

Уход за вещью, если в массиве нет 1, и при этом продукт не должен быть 1 в этом случае. Вот мой код:

#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;
}

Ответ 6

Результат O (n). Найдите последовательные элементы, которые дают максимальный продукт, умножая каждый элемент слева направо и сохраняя их в списке. Если новый продукт больше последнего, умножьте следующий элемент и обновите список. Если не начать новый список и повторить. Алгоритм в 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 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))

Возвращает:

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

Ответ 7

Я написал ниже код, чтобы найти максимальный продукт смежных целочисленных значений во входном массиве, предполагая, что продукт также будет находиться в диапазоне int он будет перебирать цикл в n/2 раза только

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;

}

Ответ 8

В Java я пытался выполнить ваш код, но не получил желаемого результата. Пожалуйста, найдите код ниже и дайте мне знать, если мне нужно что-то изменить:

открытый класс FindMax {

public static void main(String[] args) {
    float[] arr = {1.4f,1.0f,23.0f,14.5f,15.0f,15.5f};
    int n = arr.length;
    float max = find_maximum(arr, n);
    System.out.print(max);
}

static float find_maximum(float arr[], int n) {

    if (n <= 0) return 0;

    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 = Math.max(arr[i], Math.max((arr[i] * prev_min_at), (arr[i] * prev_max_at)));
        min_at = Math.min(arr[i], Math.min(arr[i] * prev_min_at, arr[i] * prev_max_at));
        max_value = Math.max(max_value, max_at);
    }
    return max_value;
}

}