オンサイト インタビューで、このアルゴリズムに関する質問をされました。NDA への署名を求められなかったので、回答のためにここに投稿します。
0 を含まないREAL数の配列を指定して、最大の積を生成する連続する要素を見つけます。アルゴリズムは線形時間で実行する必要があります
私は次のアプローチを検討しました: 2 つの配列を使用します。最初の 1 つは、DP のアイデアを使用して現在の最大絶対値積を記録することです。2 番目の配列は、これまでに満たされた負の要素の数を記録します。最終結果は、最大の最大絶対値であり、負の数は偶数である必要があります。
私の方法はうまくいくと思っていましたが、コーディング中にうまくいかないと言って中断されました。上記のアプローチで何が欠けているか教えてください。
アルゴリズムは確かに 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;
}
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²)時間で実行される
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 )
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
負の数は今のところ無視しています...
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])
入力配列内の隣接する整数値の最大積を見つけるために、以下のコードを書きました。積も 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;
}
配列に 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;
}