Как найти наивысший продукт из k элементов в массиве n длины, где k <n

Question

Недавно я попробовал вопрос о наивысшем продукте из 3 элементов. Теперь я пытаюсь сделать это для k элементов. Скажем, из 3 теперь он просит 4 элемента. Я попытался написать общую функцию, чтобы она могла обрабатывать любые k элементов в массиве. Алго должно быть в O (n) точно так же, как и с тремя элементами.

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

Выход: Раствор

503440 

Answer 2

O (п) в numpy, стресс-тестирование на 4 примера списки и беспощадной автоматический тестовый сценарий @Stefan Pochmann в. Большое спасибо Стефану, без чьих-либо слов пара серьезных ошибок осталась бы незамеченной.

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) 

Краткого описание алгоритма:

• специального случай к нечетному, всем данным отрицательной находки к наималейшему отрицательному по перегородке, вернуть прод, остановить
• раздел по абсолютной величине, расщеплению при ранге к - O (n) в худшем случае с библиотечной функцией introselect
• , если prod top k> = 0, stop
• , если возможно, подкачка наименее положительная внутри для большинства отрицательных внешних, хранить prod
• если возможно своп наималейшего отрицательные внутри для большинства положительно снаружи, магазин прод
• возвращения лучших выше, остановить

Пример запуск:

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