如何在n長度的數組中找到k個元素的最高積，其中k <n

Question

我最近嘗試了3個元素的最高產品的問題。現在我正在努力爲k元素做到這一點。現在從3開始說它要求4個元素。我試圖編寫一個通用函數，以便它可以處理數組中的任何k個元素。算法必須在O（n）中，就像具有3個元素的算子一樣。

def highest_product_sol(input): 

    high = max(input[0],input[1]) 
    low = min(input[0],input[1]) 


    max_prod_2 = input[0] * input[1] 
    low_prod_2 = input[0] * input[1] 
    max_prod_3 = max_prod_2 * input[2] 


    prod_2_high = input[0] * input[1] 
    prod_2_low = input[0] * input[1] 

    for i in range(2,len(input)): 
     val = input[i] 
     max_prod_3 = max(max_prod_3,max_prod_2*val,low_prod_2*val) 

     prod_2_high = high * val 
     prod_2_low = low * val 

     max_prod_2 = max(max_prod_2,prod_2_high) 

     low_prod_2 = min(low_prod_2,prod_2_high) 


     high = max(high,val) 

     low = min(low,val) 


    return (max_prod_2,low_prod_2,max_prod_3) 

def highest_product_num(input,num): 


    high = max(input[0:num - 1]) 
    low = min(input[0:num - 1]) 


    print("max",high) 
    print("min",low) 

    prod_high_minus_1 = 1 
    prod_low_minus_1 = 1 

    for n in range(0,num-1): 
     prod_high_minus_1 *= input[n] 
     prod_low_minus_1 *= input[n] 

    max_prod_n_1 = prod_high_minus_1 
    min_prod_n_1 = prod_high_minus_1 
    max_prod_n = prod_high_minus_1 * input[num-1] 

    for i in range(num,len(input)): 
     val = input[i] 
     max_prod_n = max(max_prod_n,max_prod_n_1*val,min_prod_n_1*val) 

     prod_high_minus_1 = high * val 
     prod_low_minus_1 = low * val 

     max_prod_n_1 = max(max_prod_n_1,prod_high_minus_1) 

     min_prod_n_1 = min(min_prod_n_1,prod_low_minus_1) 


     high = max(high,val) 

     low = min(low,val) 

    return max_prod_n 
test_input = [[1,2,3,4,5,6,7,8],[1,-2,3,4,5,100,2,3,1],[-10,-10,1,3,2][1000,7,-6,2,2]] 
print(test_input) 

for i in test_input: 
    print(highest_product_num(i,4),"\n") 

# correct `results` 
# 1680 
# 6000 
# 600 

Answer 1

from functools import reduce 
import operator 

def get_largest_product(l,n): 
    possible_products = [reduce(operator.mul,c,1) for c in combinations(l, n)] 
    return max(possible_products) 

print (get_largest_product([232,434,5,4],3)) 

輸出：在numpy

503440 

Answer 2

O（n）的溶液中，壓力測試的實施例4名的列表和@Stefan Pochmann的無情自動測試腳本。非常感謝Stefan，如果沒有他們的投入，一些嚴重的錯誤將不會被忽視。

import numpy as np 

def kmaxprod_v2(data, k): 
    if len(data) < k: 
     return np.nan 
    data = np.asanyarray(data) 
    # for integer dtypes convert to python ints to have unlimited range for the 
    # final product 
    dfp = data.astype(object) if data.dtype in (
     int, np.int64, np.int32, np.int16, np.int8) else data 
    # np.argpartition raises an exception if len(data) == k, therefore 
    if len(data) == k: 
     return np.prod(dfp) 
    neg = data <= 0 
    # if k is odd and there are no positive elements we must settle for the 
    # least negative 
    if k % 2 == 1 and np.count_nonzero(neg) == len(data): 
     return np.prod(-np.partition(-data, k)[:k].astype(dfp.dtype)) 
    # now n > k and we have at least one positive element 
    ap = np.argpartition(-np.absolute(data), k) 
    low, high = ap[k:], ap[:k] 
    # try multiplying the k with highest absolute value 
    greedy = np.prod(dfp[high]) 
    if greedy >= 0: 
     return greedy 
    # there are two possible ways of fixing the sign: 
    # either swap the worst negative inside for the best positive outside 
    # or swap the worst positive inside for the best negative outside 
    # compute both and compare 
    # bpo in, wni out 
    bpo = np.max(dfp[low]) 
    if bpo <= 0: 
     spfn = 0 
    else: 
     neg_high = np.where(neg[high])[0] 
     wni_ind = np.argmax(data[high[neg_high]]) 
     # translate to index in high 
     wni_ind = neg_high[wni_ind] 
     spfn = bpo*np.prod(dfp[high[:wni_ind]])*np.prod(dfp[high[wni_ind+1:]]) 
    # bno in, wno out 
    pos_high = np.where(~neg[high])[0] 
    if len(pos_high) == 0: 
     snfp = 0 
    else: 
     wpi_ind = np.argmin(data[high[pos_high]]) 
     wpi_ind = pos_high[wpi_ind] 
     bno = np.min(dfp[low]) 
     snfp = bno*np.prod(dfp[high[:wpi_ind]])*np.prod(dfp[high[wpi_ind+1:]]) 
    return max(spfn, snfp) 

算法中的簡要說明：

• 特殊情況k個奇數，所有數據負得到k通過分區至少負，返回督促，k級的絕對值，分裂停止
• 分區 - O（n）使用內置庫函數的最壞情況
• 如果產品頂部k> = 0，則停止
• 如果可能的話，交換最不積極的內部最外面的負數，店面產品
• 如果可能的話交換至少負內部的最積極外，店內督促
• 回報最好的上方，停止

採樣運行：

>>> test_input = [[1,2,3,4,5,6,7,8],[1,-2,3,4,5,100,2,3,1],[-10,-10,1,3,2],[1000,7,-6,2,2]] 
>>> for t in test_input: 
...  kmp.kmaxprod(t,4) 
... 
1680 
6000 
600 
28000 

測試腳本，感謝@Stefan Pochmann

import itertools, operator, functools, time 
def naive(data, k): 
    return max(functools.reduce(operator.mul, comb) for comb in itertools.combinations(data, k)) 

test_input = [([1,2,3,4,5,6,7,8], 4), ([1,-2,3,4,5,100,2,3,1], 4), 
       ([-10,-10,1,3,2], 4), ([1000,7,-6,2,2],4), 
       ([-1, 0, 1], 2), ([2, 5, 8, 9, 1, 3, 7], 4), 
       ([-1, -1, 2, 1], 2), ([-1000, -1, 2, 3], 2), 
       ([3, 5, 2, 8, 3], 2), ([-1000, -1, 2, 3, 4, 5, 6, 7], 2)] 

for t, k in test_input: 
    print(t, k, kmaxprod_v2(t, k), naive(t, k)) 

ne = 0 
t = np.zeros((3,)) 
import random 
for k in range(2, 20): 
    for n in range(k, 24): 
    print('n =', n, ': k =', k, 'errors:', ne, 'total time O(n), naive:', np.diff(t)) 
    for _ in range(100): 
     data = [random.randrange(-14, 15) for _ in range(n)] 
     t[0] += time.time() 
     a = kmaxprod_v2(data, k) 
     t[1] += time.time() 
     b = naive(data, k) 
     t[2] += time.time() 
     if a != b: 
      ne += 1 
      print(data, k, a, b)