22

我在现场面试时被问到这个算法问题。由于没有要求我签署 NDA，因此我将其发布在这里以寻求答案。

给定一个不包含 0的实数数组，找到产生最大乘积的连续元素。算法应该在线性时间内运行

我考虑了以下方法：使用两个数组。第一个是使用DP思想记录当前最大绝对值乘积，第二个数组记录到目前为止遇到的负元素的数量。最终的结果应该是最大的最大绝对值并且负数的个数是偶数。

我以为我的方法会起作用，但在编码过程中被打断说它不起作用。请让我知道上述方法中缺少什么。

4

9 回答 9

42

该算法确实是 O(n)。迭代数组时，使用一个变量来存储到目前为止找到的最大值，一个变量来存储以 a[i] 结尾的子数组的最大值，另一个变量来存储以 a[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;
}
于 2013-09-17T02:13:01.087 回答
2

您可以实现 Kadane 算法的变体（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²)时间中运行

于 2013-09-17T01:28:29.653 回答
0

暂时忽略负数...

让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])

于 2013-09-17T05:54:35.183 回答
0

使用 python 符号：

  • 计算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 )
于 2013-09-17T03:36:43.037 回答
0

如果我们想在O(n)中求解并允许两次遍历数组和o(n)额外空间，我下面的代码将适用于 Java 中的所有+ve和-ve值。

import java.util.ArrayList;
import java.util.List;

public class largestProductOfTwoNumbers {

    public static void main(String[] args) {
        int result = 0;
        int a[] = { -22, -5, 12, 6, 3, 4, 9, -11, 4, 5, 6, 8, 7, 7 };
        int max = 0;

        int curr = 0;
        List<Integer> list = new ArrayList();

        for (int i = 0; i < a.length - 1; i++) {

            curr = a[i] * a[i + 1];
            list.add(curr);

        }

        for (int i = 0; i < list.size(); i++) {
            if (list.get(i) > max) {
                max = list.get(i);
            }

        }
        System.out.println(max);
    }
}
于 2019-10-26T16:45:01.010 回答
0

如果数组中没有 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;
}
于 2015-07-29T06:13:16.803 回答
0

这个答案假设所有数字都是正数。

python中的单行解决方案：

from itertools import accumulate

def max_prod(a):
    return max(accumulate(a, lambda x,y: max(x*y, 1), initial=1))

这是 O(n) 时间和 O(1) 空间。

该算法用于itertools.accumulate从数组的开头计算累积乘积，如果结果小于 1，则返回空乘积 1。然后，我们返回找到的最大乘积。

我们可以通过生成随机数数组并与蛮力解决方案进行比较来测试算法的正确性：

from math import prod
from numpy import random

def brute_force(a):
    return max(prod(a[i:j]) for i in range(len(a)) for j in range(i,len(a)+1))

for _ in range(1000):
    a = random.random(10) * 3 # array of 10 floats in [0.0..3.0]
    p1 = max_prod(a)
    p2 = brute_force(a)
    if p1 != p2:
        print(a)
        print(list(accumulate(a, lambda x,y: max(x*y, 1), initial=1)))
        print(p1, p2)
        print()
于 2021-11-25T15:29:09.200 回答
0

我写了下面的代码，用于查找输入数组中相邻整数值的最大乘积，假设乘积也在 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;

}
于 2017-03-28T02:26:41.587 回答
0

在 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'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))

返回：

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
于 2015-09-18T20:10:06.747 回答